License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2015.187
URN: urn:nbn:de:0030-drops-55821
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5582/
Go to the corresponding LIPIcs Volume Portal

ten Brinke, Chiel B. ; van Houten, Frank J. P. ; Bodlaender, Hans L.

Practical Algorithms for Linear Boolean-width

pdf-format:
19.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{tenbrinke_et_al:LIPIcs:2015:5582,
  author =	{Chiel B. ten Brinke and Frank J. P. van Houten and Hans L. Bodlaender},
  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 =	{Thore Husfeldt and Iyad Kanj},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5582},
  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}
}

Keywords: graph decomposition, boolean-width, heuristics, exact algorithms, vertex subset problems
Collection: 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Issue Date: 2015
Date of publication: 19.11.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI