@inproceedings{e05ef4608e0b4c7c8c43b6c14040782e,
title = "Faster computation of path-width",
abstract = "Tree-width and path-width are widely successful concepts.Many NP-hard problems have efficient solutions when restricted to graphs of bounded tree-width.Many efficient algorithms are based on a tree decomposition.Sometimes the more restricted path decomposition is required.The bottleneck for such algorithms is often the computation of the width and a corresponding tree or path decomposition.For graphs with n vertices and tree-width or path-width k, the standard linear time algorithm to compute these decompositions dates back to 1996.Its running time is linear in n and exponential in k3 and not usable in practice.Here we present a more efficient algorithm to compute the path-width and provide a path decomposition.Its running time is 2O(k2)n.In the classical algorithm of Bodlaender and Kloks, the path decomposition is computed from a tree decomposition.Here, an optimal path decomposition is computed from a path decomposition of about twice the width.The latter is computed from a constant factor smaller graph.",
author = "Martin F{\"u}rer",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 27th International Workshop on Combinatorial Algorithms, IWOCA 2016 ; Conference date: 17-08-2016 Through 19-08-2016",
year = "2016",
doi = "10.1007/978-3-319-44543-4_30",
language = "English (US)",
isbn = "9783319445427",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "385--396",
editor = "Veli M{\"a}kinen and Puglisi, {Simon J.} and Leena Salmela",
booktitle = "Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Proceedings",
address = "Germany",
}