Volume

Dagstuhl Seminar Proceedings, Volume 8431

Publication Details

  • published at: 2008-12-23
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.08431.1
08431 Abstracts Collection – Moderately Exponential Time Algorithms

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

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.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
DOI: 10.4230/DagSemProc.08431.2
08431 Executive Summary – Moderately Exponential Time Algorithms

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

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.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
DOI: 10.4230/DagSemProc.08431.3
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

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.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
DOI: 10.4230/DagSemProc.08431.4
Spanning Trees of Bounded Degree Graphs

Authors: John Michael Robson

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.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.}
}

Filters

  • Authors
  • F
  • Fomin, Fedor V.
  • I
  • Iwama, Kazuo
  • K
  • Kaski, Petteri
  • Koivisto, Mikko
  • Kowalik, Lukasz
  • Kratsch, Dieter
  • O
  • Okamoto, Yoshio
  • R
  • Robson, John Michael
  • V
  • van Rooij, Johan
  • W
  • Williams, Ryan

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact