TY - GEN

T1 - Improved Self-Reduction Algorithms for Graphs with Bounded Treewidth

AU - Bodlaender, Hans

PY - 1990

Y1 - 1990

N2 - Recent results of Robertson and Seymour show, that every class that is closed under taking of minors can be recognized in O (n^3) time. If there is a fixed upper bound on the treewidth of the graphs in the class, i.e. if there is a planar graph not in the class, then the class can be recognized in O(n^2) time. However, this result is non-constructive in two ways: the algorithm only decides on membership, but does not construct ‘a solution’, e.g. a linear ordering, decomposition or embedding; and no method is given to find the algorithms. In many cases, both non-constructive elements can be avoided, using techniques of Fellows and Langston, based on self-reduction. In this paper we introduce two techniques that help to reduce the running time of self-reduction algorithms. With help of these techniques we show that there exist O (n^2) algorithms, that decide on membership and construct solutions for treewidth, pathwidth, search number, vertex search number, node search number, cutwidth, modified cutwidth, vertex separation number, gate matrix layout, and progressive black-white pebbling, where in each case the parameter k is a fixed constant.

AB - Recent results of Robertson and Seymour show, that every class that is closed under taking of minors can be recognized in O (n^3) time. If there is a fixed upper bound on the treewidth of the graphs in the class, i.e. if there is a planar graph not in the class, then the class can be recognized in O(n^2) time. However, this result is non-constructive in two ways: the algorithm only decides on membership, but does not construct ‘a solution’, e.g. a linear ordering, decomposition or embedding; and no method is given to find the algorithms. In many cases, both non-constructive elements can be avoided, using techniques of Fellows and Langston, based on self-reduction. In this paper we introduce two techniques that help to reduce the running time of self-reduction algorithms. With help of these techniques we show that there exist O (n^2) algorithms, that decide on membership and construct solutions for treewidth, pathwidth, search number, vertex search number, node search number, cutwidth, modified cutwidth, vertex separation number, gate matrix layout, and progressive black-white pebbling, where in each case the parameter k is a fixed constant.

U2 - 10.1007/3-540-52292-1_17

DO - 10.1007/3-540-52292-1_17

M3 - Conference contribution

SN - 978-3-540-52292-8

VL - 411

T3 - Lecture Notes in Computer Science

SP - 232

EP - 244

BT - Graph-Theoretic Concepts in Computer Science

A2 - Nagl, Manfred

PB - Springer

T2 - 15th International Workshop on Graph-Theoretic Concepts in Computer Science, WG'89

Y2 - 14 June 1989 through 16 June 1989

ER -