An improved algorithm for finding tree decompositions of small width

From MaRDI portal
(Redirected from An improved algorithm for finding tree decompositions of small width)
An improved algorithm for finding tree decompositions of small width (scientific article; zbMATH DE number 1420905)





In [SIAM J. Comput. 25, No. 6, 1305-1317 (1996; Zbl 0864.68074)], for each constant \(k\), a linear time algorithm was given by H. L. Bodlaender, that given a graph \(G\), decides if \(G\) has treewidth at most \(k\), and if so, finds a tree decomposition of \(G\) of width at most \(k\). This paper gives a modification of that algorithm. The modification does in addition the following: when the input graph \(G\) has treewidth more than \(k\), then a subgraph \(G'\) of \(G\) is obtained, such that the treewidth of \(G'\) is between \(k+1\) and \(2k\); the output consists of \(G'\) and a tree decomposition of \(G'\) of width at most \(2k\). This modified algorithm can be used as a subroutine for an algorithm of the \(l\)-disjoint rooted paths problem. In this problem, \(l\) disjoint pairs of vertices are given, and the question is if there are mutually vertex-disjoint paths between every given pair. The result of this paper shows that this problem can be solved in \(O(n^2)\) time. For the entire collection see [Zbl 0929.00074].











This page was built for publication: An improved algorithm for finding tree decompositions of small width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4944974)