Volume

Dagstuhl Seminar Proceedings, Volume 10441

Publication Details

  • published at: 2011-01-27
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.10441.1
10441 Abstracts Collection – Exact Complexity of NP-hard Problems

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

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.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
DOI: 10.4230/DagSemProc.10441.2
Listing all maximal cliques in sparse graphs in near-optimal time

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

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

Filters

  • Authors
  • E
  • Eppstein, David
  • H
  • Husfeldt, Thore
  • K
  • Kratsch, Dieter
  • L
  • Löffler, Maarten
  • P
  • Paturi, Ramamohan
  • S
  • Sorkin, Gregory B.
  • Strash, Darren

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