1 Search Results for "Pino, Willem J. A."

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

Refine by Author
1 Bodlaender, Hans L.
1 Pino, Willem J. A.
1 van Rooij, Johan M. M.

Refine by Classification

Refine by Keyword
1 Branchwidth
1 Dynamic Programming
1 Graph algorithms
1 Planar Graphs
1 Treewidth

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Pino, Willem J. A."

Cut and Count and Representative Sets on Branch Decompositions

Abstract

Cite as

Thanks for your feedback!

Could not send message