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 -