TY - CHAP
T1 - Better algorithms for the pathwidth and treewidth of graphs
AU - Bodlaender, Hans
AU - Kloks, Ton
PY - 1991
Y1 - 1991
N2 - In this paper we give, for all constants k, explicit O(n log^2 n) algorithms, that given a graph G = (V,E), decide whether the treewidth (or pathwidth) of G is at most k, and if so, find a tree-decomposition or (path-decomposition) of G with treewidth (or pathwidth) at most k. In contrast with previous solutions, our algorithms do not rely on non-constructive reasoning, and are single exponential in k. This result implies a similar result for several graph notions that are equivalent with treewidth or pathwidth.
AB - In this paper we give, for all constants k, explicit O(n log^2 n) algorithms, that given a graph G = (V,E), decide whether the treewidth (or pathwidth) of G is at most k, and if so, find a tree-decomposition or (path-decomposition) of G with treewidth (or pathwidth) at most k. In contrast with previous solutions, our algorithms do not rely on non-constructive reasoning, and are single exponential in k. This result implies a similar result for several graph notions that are equivalent with treewidth or pathwidth.
U2 - 10.1007/3-540-54233-7_162
DO - 10.1007/3-540-54233-7_162
M3 - Chapter
SN - 978-3-540-54233-9
VL - 510
T3 - Lecture Notes in Computer Science
SP - 544
EP - 555
BT - Automata, Languages and Programming
A2 - Albert, Javier Leach
A2 - Monien, Burkhard
A2 - Artalejo, Mario Rodríguez
PB - Springer
ER -