AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
From MaRDI portal
Publication:5249045
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
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
