3 Search Results for "van Rooij, Johan"


Document
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
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
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 Fomin, Fedor V.
  • 1 Iwama, Kazuo
  • 1 Kaski, Petteri
  • Show More...

  • Refine by Classification

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

  • Refine by Type
  • 3 document

  • Refine by Publication Year
  • 2 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