AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
From MaRDI portal
Publication:5249045
DOI10.1142/S0129054100000247zbMath1320.05128WikidataQ127705816 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
68Q25: Analysis of algorithms and problem complexity
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, The Parameterized Complexity of Graph Cyclability, Walking through waypoints, Coloring immersion-free graphs, The disjoint paths problem in quadratic time, The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, MSOL restricted contractibility to planar graphs, Online promise problems with online width metrics, A faster parameterized algorithm for pseudoforest deletion, A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Computing crossing numbers in quadratic time, Linear time algorithms for two disjoint paths problems on directed acyclic graphs, Optimal tree decompositions revisited: a simpler linear-time FPT algorithm, Obtaining a planar graph by vertex deletion, The relative clique-width of a graph, A $c^k n$ 5-Approximation Algorithm for Treewidth, Faster Computation of Path-Width, A Very Practical Algorithm for the Two-Paths Problem in 3-Connected Planar Graphs, Obtaining a Planar Graph by Vertex Deletion, Improved Algorithms for the 2-Vertex Disjoint Paths Problem
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
