Practical algorithms for branch-decompositions of planar graphs
From MaRDI portal
Publication:896665
DOI10.1016/j.dam.2014.12.017zbMath1326.05035OpenAlexW2095382269MaRDI QIDQ896665
Mingzhe Zhu, Zhengbing Bian, Qian-Ping Gu
Publication date: 10 December 2015
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2014.12.017
Analysis of algorithms (68W40) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Subexponential parameterized algorithms
- Linearity of grid minors in treewidth with applications through bidimensionality
- Computational study on planar dominating set problem
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Graph minors. XIII: The disjoint paths problem
- Random sampling of large planar maps and convex polyhedra
- Planar Branch Decompositions I: The Ratcatcher
- Planar Branch Decompositions II: The Cycle Method
- Easy problems for tree-decomposable graphs
- New upper bounds on the decomposability of planar graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Complexity of Finding Embeddings in a k-Tree
- TSPLIB—A Traveling Salesman Problem Library
- Constructive linear time algorithms for branchwidth
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
