DROPS

Document

DOI: 10.4230/LIPIcs.IPEC.2015.187

Practical Algorithms for Linear Boolean-width

Authors: Chiel B. ten Brinke, Frank J. P. van Houten, and Hans L. Bodlaender

Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)

Abstract

In this paper, we give a number of new exact algorithms and heuristics to compute linear boolean decompositions, and experimentally evaluate these algorithms. The experimental evaluation shows that significant improvements can be made with respect to running time without increasing the width of the generated decompositions. We also evaluated dynamic programming algorithms on linear boolean decompositions for several vertex subset problems. This evaluation shows that such algorithms are often much faster (up to several orders of magnitude) compared to theoretical worst case bounds.

Cite as

Chiel B. ten Brinke, Frank J. P. van Houten, and Hans L. Bodlaender. Practical Algorithms for Linear Boolean-width. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 187-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{tenbrinke_et_al:LIPIcs.IPEC.2015.187,
  author =	{ten Brinke, Chiel B. and van Houten, Frank J. P. and Bodlaender, Hans L.},
  title =	{{Practical Algorithms for Linear Boolean-width}},
  booktitle =	{10th International Symposium on Parameterized and Exact Computation (IPEC 2015)},
  pages =	{187--198},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-92-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{43},
  editor =	{Husfeldt, Thore and Kanj, Iyad},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.187},
  URN =		{urn:nbn:de:0030-drops-55821},
  doi =		{10.4230/LIPIcs.IPEC.2015.187},
  annote =	{Keywords: graph decomposition, boolean-width, heuristics, exact algorithms, vertex subset problems}
}

Search Results

Documents authored by ten Brinke, Chiel B.

Practical Algorithms for Linear Boolean-width

Abstract

Cite as

Thanks for your feedback!

Could not send message