2 Search Results for "van Rooij, Johan M. M."

Document
DOI: 10.4230/LIPIcs.IPEC.2016.27
Cut and Count and Representative Sets on Branch Decompositions

Authors: Willem J. A. Pino, Hans L. Bodlaender, and Johan M. M. van Rooij

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
Recently, new techniques have been introduced to speed up dynamic programming algorithms on tree decompositions for connectivity problems: the 'Cut and Count' method and a method called the rank-based approach, based on representative sets and Gaussian elimination. These methods respectively give randomised and deterministic algorithms that are single exponential in the treewidth, and polynomial, respectively linear in the number of vertices. In this paper, we adapt these methods to branch decompositions yielding algorithms, both randomised and deterministic, that are in many cases faster than when tree decompositions would be used. In particular, we obtain the currently fastest randomised algorithms for several problems on planar graphs. When the involved weights are O(n^{O(1)}), we obtain faster randomised algorithms on planar graphs for Steiner Tree, Connected Dominating Set, Feedback Vertex Set and TSP, and a faster deterministic algorithm for TSP. When considering planar graphs with arbitrary real weights, we obtain faster deterministic algorithms for all four mentioned problems.
Cite as

Willem J. A. Pino, Hans L. Bodlaender, and Johan M. M. van Rooij. Cut and Count and Representative Sets on Branch Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 27:1-27:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{pino_et_al:LIPIcs.IPEC.2016.27,
  author =	{Pino, Willem J. A. and Bodlaender, Hans L. and van Rooij, Johan M. M.},
  title =	{{Cut and Count and Representative Sets on Branch Decompositions}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{27:1--27:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.27},
  URN =		{urn:nbn:de:0030-drops-69450},
  doi =		{10.4230/LIPIcs.IPEC.2016.27},
  annote =	{Keywords: Graph algorithms, Branchwidth, Treewidth, Dynamic Programming, Planar Graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1329
Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set

Authors: Johan M. M. van Rooij and Hans L. Bodlaender

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems, like Dominating Set and Independent Set. In this paper, we propose to use measure and conquer also as a tool in the design of algorithms. In an iterative process, we can obtain a series of branch and reduce algorithms. A mathematical analysis of an algorithm in the series with measure and conquer results in a quasiconvex programming problem. The solution by computer to this problem not only gives a bound on the running time, but also can give a new reduction rule, thus giving a new, possibly faster algorithm. This makes design by measure and conquer a form of computer aided algorithm design. When we apply the methodology to a Set Cover modelling of the Dominating Set problem, we obtain the currently fastest known exact algorithms for Dominating Set: an algorithm that uses $O(1.5134^n)$ time and polynomial space, and an algorithm that uses $O(1.5063^n)$ time.
Cite as

Johan M. M. van Rooij and Hans L. Bodlaender. Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 657-668, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{vanrooij_et_al:LIPIcs.STACS.2008.1329,
  author =	{van Rooij, Johan M. M. and Bodlaender, Hans L.},
  title =	{{Design by Measure and Conquer, A Faster Exact Algorithm for Dominating Set}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{657--668},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1329},
  URN =		{urn:nbn:de:0030-drops-13297},
  doi =		{10.4230/LIPIcs.STACS.2008.1329},
  annote =	{Keywords: Exact algorithms, exponential time algorithms, branch and reduce, measure and conquer, dominating set, computer aided algorithm design}
}
  • Refine by Author
  • 2 Bodlaender, Hans L.
  • 2 van Rooij, Johan M. M.
  • 1 Pino, Willem J. A.

  • Refine by Classification

  • Refine by Keyword
  • 1 Branchwidth
  • 1 Dynamic Programming
  • 1 Exact algorithms
  • 1 Graph algorithms
  • 1 Planar Graphs
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2008
  • 1 2017

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