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].
- An improved algorithm for finding tree decompositions of small width
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Tree-decompositions of small pathwidth
- Tree decompositions with small cost
- Tree decompositions with small cost
- SAT-based local improvement for finding tree decompositions of small width
- Subexponential time algorithms for finding small tree and path decompositions
- Tree decompositions of small diameter
- A simple linear-time algorithm for finding path-decompositions of small width
- scientific article; zbMATH DE number 1031380
- A linear time algorithm for monadic querying of indefinite data over linearly ordered domains
- Finding good tree decompositions by local search
- Finding small separators in linear time via treewidth reduction
- Irrelevant vertices for the planar disjoint paths problem
- An Iterative Heuristic Algorithm for Tree Decomposition
- Algorithms for solving problems on graphs of bounded pathwidth
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- An improved algorithm for finding tree decompositions of small width
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)