AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH

DOI10.1142/S0129054100000247zbMath1320.05128OpenAlexW1972515959WikidataQ127705816 ScholiaQ127705816MaRDI QIDQ5249045

Ljubomir Perković, Bruce A. Reed

Publication date: 29 April 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054100000247

zbMATH Keywords

treewidthtree decompositionsdisjoint rooted paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Computing crossing numbers in quadratic time, Coloring immersion-free graphs, The relative clique-width of a graph, Online promise problems with online width metrics, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, The disjoint paths problem in quadratic time, A faster parameterized algorithm for pseudoforest deletion, A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs, Obtaining a Planar Graph by Vertex Deletion, Obtaining a planar graph by vertex deletion, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, MSOL restricted contractibility to planar graphs, Improved Algorithms for the 2-Vertex Disjoint Paths Problem, A $c^k n$ 5-Approximation Algorithm for Treewidth, The Parameterized Complexity of Graph Cyclability, Walking through waypoints, Faster Computation of Path-Width, Optimal tree decompositions revisited: a simpler linear-time FPT algorithm, Unnamed Item

Cites Work

• Graph minors. VI. Disjoint paths across a disc
• On the connectivity function of a matroid
• A partial k-arboretum of graphs with bounded treewidth
• Graph minors. XIII: The disjoint paths problem
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth