13 Search Results for "Kratsch, Dieter"


Document
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration

Authors: Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)


Abstract
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into one whose size is bounded by the parameter plus a solution-lifting algorithm that efficiently enumerates all solutions from the set of the solutions of the kernel. We propose to consider two new versions of enumeration kernels by asking that the solutions of the original instance can be enumerated in polynomial time or with polynomial delay from the kernel solutions. Using the NP-hard Matching Cut problem parameterized by structural parameters such as the vertex cover number or the cyclomatic number of the input graph, we show that the new enumeration kernels present a useful notion of data reduction for enumeration problems which allows to compactly represent the set of feasible solutions.

Cite as

Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.STACS.2021.37,
  author =	{Golovach, Petr A. and Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang},
  title =	{{Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{37:1--37:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.37},
  URN =		{urn:nbn:de:0030-drops-136823},
  doi =		{10.4230/LIPIcs.STACS.2021.37},
  annote =	{Keywords: enumeration problems, polynomial delay, output-sensitive algorithms, kernelization, structural parameterizations, matching cuts}
}
Document
Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms

Authors: Christian Komusiewicz, Dieter Kratsch, and Van Bang Le

Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)


Abstract
In a graph, a matching cut is an edge cut that is a matching. Matching Cut, which is known to be NP-complete, is the problem of deciding whether or not a given graph G has a matching cut. In this paper we show that Matching Cut admits a quadratic-vertex kernel for the parameter distance to cluster and a linear-vertex kernel for the parameter distance to clique. We further provide an O^*(2^{dc(G)}) time and an O^*(2^{dc^-}(G)}) time FPT algorithm for Matching Cut, where dc(G) and dc^-(G) are the distance to cluster and distance to co-cluster, respectively. We also improve the running time of the best known branching algorithm to solve Matching Cut from O^*(1.4143^n) to O^*(1.3803^n). Moreover, we point out that, unless NP subseteq coNP/poly, Matching Cut does not admit a polynomial kernel when parameterized by treewidth.

Cite as

Christian Komusiewicz, Dieter Kratsch, and Van Bang Le. Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 19:1-19:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{komusiewicz_et_al:LIPIcs.IPEC.2018.19,
  author =	{Komusiewicz, Christian and Kratsch, Dieter and Le, Van Bang},
  title =	{{Matching Cut: Kernelization, Single-Exponential Time FPT, and Exact Exponential Algorithms}},
  booktitle =	{13th International Symposium on Parameterized and Exact Computation (IPEC 2018)},
  pages =	{19:1--19:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-084-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{115},
  editor =	{Paul, Christophe and Pilipczuk, Michal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.19},
  URN =		{urn:nbn:de:0030-drops-102207},
  doi =		{10.4230/LIPIcs.IPEC.2018.19},
  annote =	{Keywords: matching cut, decomposable graph, graph algorithm}
}
Document
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs

Authors: Frank Kammer, Dieter Kratsch, and Moritz Laudahn

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)


Abstract
We present space-efficient algorithms for computing cut vertices in a given graph with n vertices and m edges in linear time using O(n+min{m,n log log n}) bits. With the same time and using O(n+m) bits, we can compute the biconnected components of a graph. We use this result to show an algorithm for the recognition of (maximal) outerplanar graphs in O(n log log n) time using O(n) bits.

Cite as

Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{kammer_et_al:LIPIcs.MFCS.2016.56,
  author =	{Kammer, Frank and Kratsch, Dieter and Laudahn, Moritz},
  title =	{{Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.56},
  URN =		{urn:nbn:de:0030-drops-64683},
  doi =		{10.4230/LIPIcs.MFCS.2016.56},
  annote =	{Keywords: graph algorithms, space efficiency, cut vertices, maximal outerplanar graphs}
}
Document
A Linear Kernel for Finding Square Roots of Almost Planar Graphs

Authors: Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)


Abstract
A graph H is a square root of a graph G if G can be obtained from H by the addition of edges between any two vertices in H that are of distance 2 of each other. The Square Root problem is that of deciding whether a given graph admits a square root. We consider this problem for planar graphs in the context of the "distance from triviality" framework. For an integer k, a planar+kv graph is a graph that can be made planar by the removal of at most k vertices. We prove that the generalization of Square Root, in which we are given two subsets of edges prescribed to be in or out of a square root, respectively, has a kernel of size O(k) for planar+kv graphs, when parameterized by k. Our result is based on a new edge reduction rule which, as we shall also show, has a wider applicability for the Square Root problem.

Cite as

Petr A. Golovach, Dieter Kratsch, Daniël Paulusma, and Anthony Stewart. A Linear Kernel for Finding Square Roots of Almost Planar Graphs. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.SWAT.2016.4,
  author =	{Golovach, Petr A. and Kratsch, Dieter and Paulusma, Dani\"{e}l and Stewart, Anthony},
  title =	{{A Linear Kernel for Finding Square Roots of Almost Planar Graphs}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.4},
  URN =		{urn:nbn:de:0030-drops-60333},
  doi =		{10.4230/LIPIcs.SWAT.2016.4},
  annote =	{Keywords: planar graphs, square roots, linear kernel}
}
Document
Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality

Authors: Petr A. Golovach, Pinar Heggernes, and Dieter Kratsch

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)


Abstract
Listing, generating or enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input graph from various graph classes of bounded chordality. We establish enumeration algorithms as well as lower and upper bounds for the maximum number of minimal connected dominating sets in such graphs. In particular, we present algorithms to enumerate all minimal connected dominating sets of chordal graphs in time O(1.7159^n), of split graphs in time O(1.3803^n), and of AT-free, strongly chordal, and distance-hereditary graphs in time O^*(3^{n/3}), where n is the number of vertices of the input graph. Our algorithms imply corresponding upper bounds for the number of minimal connected dominating sets for these graph classes.

Cite as

Petr A. Golovach, Pinar Heggernes, and Dieter Kratsch. Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 307-318, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{golovach_et_al:LIPIcs.IPEC.2015.307,
  author =	{Golovach, Petr A. and Heggernes, Pinar and Kratsch, Dieter},
  title =	{{Enumerating Minimal Connected Dominating Sets in Graphs of Bounded Chordality}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{307--318},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.307},
  URN =		{urn:nbn:de:0030-drops-55925},
  doi =		{10.4230/LIPIcs.IPEC.2015.307},
  annote =	{Keywords: Minimal connected dominating set, exact algorithms, enumeration}
}
Document
10441 Abstracts Collection – Exact Complexity of NP-hard Problems

Authors: Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin

Published in: Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)


Abstract
A decade before NP-completeness became the lens through which Computer Science views computationally hard problems, beautiful algorithms were discovered that are much better than exhaustive search, for example Bellman's 1962 dynamic programming treatment of the Traveling Salesman problem and Ryser's 1963 inclusion--exclusion formula for the permanent.

Cite as

Thore Husfeldt, Dieter Kratsch, Ramamohan Paturi, and Gregory B. Sorkin. 10441 Abstracts Collection – Exact Complexity of NP-hard Problems. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{husfeldt_et_al:DagSemProc.10441.1,
  author =	{Husfeldt, Thore and Kratsch, Dieter and Paturi, Ramamohan and Sorkin, Gregory B.},
  title =	{{10441 Abstracts Collection – Exact Complexity of NP-hard Problems}},
  booktitle =	{Exact Complexity of NP-hard Problems},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10441},
  editor =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.1},
  URN =		{urn:nbn:de:0030-drops-29363},
  doi =		{10.4230/DagSemProc.10441.1},
  annote =	{Keywords: Complexity, Algorithms, NP-hard Problems, Exponential Time, SAT, Graphs}
}
Document
Listing all maximal cliques in sparse graphs in near-optimal time

Authors: David Eppstein, Maarten Löffler, and Darren Strash

Published in: Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)


Abstract
The degeneracy of an $n$-vertex graph $G$ is the smallest number $d$ such that every subgraph of $G$ contains a vertex of degree at most $d$. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron--Kerbosch algorithm and show that it runs in time $O(dn3^{d/3})$. We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an $n$-vertex graph with degeneracy $d$ (when $d$ is a multiple of 3 and $nge d+3$) is $(n-d)3^{d/3}$. Therefore, our algorithm matches the $Theta(d(n-d)3^{d/3})$ worst-case output size of the problem whenever $n-d=Omega(n)$.

Cite as

David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:DagSemProc.10441.2,
  author =	{Eppstein, David and L\"{o}ffler, Maarten and Strash, Darren},
  title =	{{Listing all maximal cliques in sparse graphs in near-optimal time}},
  booktitle =	{Exact Complexity of NP-hard Problems},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10441},
  editor =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.2},
  URN =		{urn:nbn:de:0030-drops-29356},
  doi =		{10.4230/DagSemProc.10441.2},
  annote =	{Keywords: Clique, backtracking, degeneracy, worst-case optimality}
}
Document
08431 Abstracts Collection – Moderately Exponential Time Algorithms

Authors: Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)


Abstract
From $19/10/2008$ to $24/10/2008$, the Dagstuhl Seminar 08431 ``Moderately Exponential Time Algorithms '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Abstracts Collection – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.1,
  author =	{Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter},
  title =	{{08431 Abstracts Collection – Moderately Exponential Time Algorithms}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.1},
  URN =		{urn:nbn:de:0030-drops-18004},
  doi =		{10.4230/DagSemProc.08431.1},
  annote =	{Keywords: Algorithms, Exponential time algorithms, Graphs, SAT}
}
Document
08431 Executive Summary – Moderately Exponential Time Algorithms

Authors: Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)


Abstract
The Dagstuhl seminar on Moderately Exponential Time Algorithms took place from 19.10.08 to 24.10.08. The 54 participants came from 18 countries. There were 27 talks and 2 open problem sessions. Talks were complemented by intensive informal discussions, and many new research directions and open problems will result from these discussions. The warm and encouraging Dagstuhl atmosphere stimulated new research projects.

Cite as

Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Executive Summary – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.2,
  author =	{Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter},
  title =	{{08431 Executive Summary – Moderately Exponential Time Algorithms}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.2},
  URN =		{urn:nbn:de:0030-drops-17976},
  doi =		{10.4230/DagSemProc.08431.2},
  annote =	{Keywords: Algorithms, NP-hard problems, Exact algorithms, Moderately Exponential Time Algorithms}
}
Document
08431 Open Problems – Moderately Exponential Time Algorithms

Authors: Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)


Abstract
Two problem sessions were part of the seminar on Moderately Exponential Time Algorithms. Some of the open problems presented at those sessions have been collected.

Cite as

Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams. 08431 Open Problems – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{fomin_et_al:DagSemProc.08431.3,
  author =	{Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter and Kaski, Petteri and Koivisto, Mikko and Kowalik, Lukasz and Okamoto, Yoshio and van Rooij, Johan and Williams, Ryan},
  title =	{{08431 Open Problems – Moderately Exponential Time Algorithms}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.3},
  URN =		{urn:nbn:de:0030-drops-17986},
  doi =		{10.4230/DagSemProc.08431.3},
  annote =	{Keywords: Algorithms, NP-hard problems, Moderately Exponential Time Algorithms}
}
Document
Spanning Trees of Bounded Degree Graphs

Authors: John Michael Robson

Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)


Abstract
We consider lower bounds on the number of spanning trees of connected graphs with degree bounded by $d$. The question is of interest because such bounds may improve the analysis of the improvement produced by memorisation in the runtime of exponential algorithms. The value of interest is the constant $beta_d$ such that all connected graphs with degree bounded by $d$ have at least $beta_d^mu$ spanning trees where $mu$ is the cyclomatic number or excess of the graph, namely $m-n+1$. We conjecture that $beta_d$ is achieved by the complete graph $K_{d+1}$ but we have not proved this for any $d$ greater than $3$. We give weaker lower bounds on $beta_d$ for $dle 11$. First we establish lower bounds on the factor by which the number of spanning trees is multiplied when one new vertex is added to an existing graph so that the new vertex has degree $c$ and the maximum degree of the resulting graph is at most $d$. In all the cases analysed, this lower bound $f_{c,d}$ is attained when the graph before the addition was a complete graph of order $d$ but we have not proved this in general. Next we show that, for any cut of size $c$ cutting a graph $G$ of degree bounded by $d$ into two connected components $G_1$ and $G_2$, the number of spanning trees of $G$ is at least the product of this number for $G_1$ and $G_2$ multiplied by the same factor $f_{c,d}$. Finally we examine the process of repeatedly cutting a graph until no edges remain. The number of spanning trees is at least the product of the multipliers associated with all the cuts. Some obvious constraints on the number of cuts of each size give linear constraints on the normalised numbers of cuts of each size which are then used to lower bound $beta_d$ by the solution of a linear program. The lower bound obtained is significantly improved by imposing a rule that, at each stage, a cut of the minimum available size is chosen and adding some new constraints implied by this rule.

Cite as

John Michael Robson. Spanning Trees of Bounded Degree Graphs. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)


Copy BibTex To Clipboard

@InProceedings{robson:DagSemProc.08431.4,
  author =	{Robson, John Michael},
  title =	{{Spanning Trees of Bounded Degree Graphs}},
  booktitle =	{Moderately Exponential Time Algorithms},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8431},
  editor =	{Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.4},
  URN =		{urn:nbn:de:0030-drops-17997},
  doi =		{10.4230/DagSemProc.08431.4},
  annote =	{Keywords: Spanning trees, memorisation, cyclomatic number, bounded degree graphs, cut, linear program.}
}
Document
07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes

Authors: Andreas Brandstädt, Klaus Jansen, Dieter Kratsch, and Jeremy P. Spinrad

Published in: Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)


Abstract
From May 20 to May 25, 2007, the Dagstuhl Seminar 07211 ``Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Andreas Brandstädt, Klaus Jansen, Dieter Kratsch, and Jeremy P. Spinrad. 07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{brandstadt_et_al:DagSemProc.07211.1,
  author =	{Brandst\"{a}dt, Andreas and Jansen, Klaus and Kratsch, Dieter and Spinrad, Jeremy P.},
  title =	{{07211 Abstracts Collection – Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes}},
  booktitle =	{Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7211},
  editor =	{Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.1},
  URN =		{urn:nbn:de:0030-drops-12697},
  doi =		{10.4230/DagSemProc.07211.1},
  annote =	{Keywords: Graph theory, approximation algorithms, certifying algorithms, exact algorithms}
}
Document
Linear-time certifying recognition for partitioned probe cographs

Authors: Van Bang Le and H.N. de Ridder

Published in: Dagstuhl Seminar Proceedings, Volume 7211, Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes (2007)


Abstract
Cographs are those graphs without induced path on four vetices. A graph $G=(V, E)$ with a partition $V=Pcup N$ where $N$ is an independent set is a partitioned probe cograph if one can add new edges between certain vertices in $N$ in such a way that the graph obtained is a cograph. We characterize partitioned probe cographs in terms of five forbidden induced subgraphs. Using this characterization, we give a linear-time recognition algorithm for partitioned probe cographs. Our algorithm produces a certificate for membership that can be checked in linear time and a certificate for non-membership that can be checked in sublinear time.

Cite as

Van Bang Le and H.N. de Ridder. Linear-time certifying recognition for partitioned probe cographs. In Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes. Dagstuhl Seminar Proceedings, Volume 7211, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{le_et_al:DagSemProc.07211.2,
  author =	{Le, Van Bang and de Ridder, H.N.},
  title =	{{Linear-time certifying recognition for partitioned probe cographs}},
  booktitle =	{Exact, Approximative, Robust and Certifying Algorithms on Particular Graph Classes},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7211},
  editor =	{Andreas Brandst\"{a}dt and Klaus Jansen and Dieter Kratsch and Jeremy P. Spinrad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07211.2},
  URN =		{urn:nbn:de:0030-drops-12703},
  doi =		{10.4230/DagSemProc.07211.2},
  annote =	{Keywords: Cograph, probe cograph, certifying graph algorithm}
}
  • Refine by Author
  • 10 Kratsch, Dieter
  • 3 Fomin, Fedor V.
  • 3 Golovach, Petr A.
  • 3 Iwama, Kazuo
  • 3 Le, Van Bang
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 4 Algorithms
  • 2 Graphs
  • 2 Moderately Exponential Time Algorithms
  • 2 NP-hard problems
  • 2 SAT
  • Show More...

  • Refine by Type
  • 13 document

  • Refine by Publication Year
  • 4 2008
  • 2 2007
  • 2 2011
  • 2 2016
  • 1 2015
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail