Practical algorithms for linear boolean-width

C.B. ten Brinke, F.J.P. van Houten, H.L. Bodlaender

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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.

Original languageEnglish
Title of host publication10th International Symposium on Parameterized and Exact Computation, IPEC 2015
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages187-198
Number of pages12
Volume43
ISBN (Electronic)9783939897927
DOIs
Publication statusPublished - 1 Nov 2015
Event10th International Symposium on Parameterized and Exact Computation (IPEC 2015) - Patras, Greece
Duration: 16 Sep 201518 Sep 2015
Conference number: 10
http://algo2015.upatras.gr/ipec

Conference

Conference10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Abbreviated titleIPEC 2015
CountryGreece
CityPatras
Period16/09/1518/09/15
Internet address

Keywords

  • Boolean-width
  • Exact algorithms
  • Graph decomposition
  • Heuristics
  • Vertex subset problems

Fingerprint Dive into the research topics of 'Practical algorithms for linear boolean-width'. Together they form a unique fingerprint.

Cite this