Practical algorithms for branch-decompositions of planar graphs

DOI10.1016/J.DAM.2014.12.017MaRDI QIDQ896665zbMATH OpenOpenAlexFDO

Authors Zhengbing Bian, Qian-Ping Gu, Mingzhe Zhu

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

zbMATH Keywords

graph algorithmsplanar graphscomputational studybranch-decomposition

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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)

Recommendations

• Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
• Planar branch decompositions. II: The cycle method
• Planar branch decompositions. I: The ratcatcher
• A linear time heuristic for the branch-decomposition of planar graphs
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Call routing and the ratcatcher
• Complexity of Finding Embeddings in a k-Tree
• Computational study on planar dominating set problem
• Constructive linear time algorithms for branchwidth
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Easy problems for tree-decomposable graphs
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XIII: The disjoint paths problem
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Linearity of grid minors in treewidth with applications through bidimensionality
• New upper bounds on the decomposability of planar graphs
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Planar branch decompositions. I: The ratcatcher
• Planar branch decompositions. II: The cycle method
• Random sampling of large planar maps and convex polyhedra
• Subexponential parameterized algorithms
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(16)

• Computing the branchwidth of interval graphs
• A combinatorial optimization algorithm for solving the branchwidth problem
• STACS 2004
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• A linear time heuristic for the branch-decomposition of planar graphs
• scientific article; zbMATH DE number 3997557 (Why is no real title available?)
• Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
• scientific article; zbMATH DE number 1990711 (Why is no real title available?)
• scientific article; zbMATH DE number 6873974 (Why is no real title available?)
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Graphs, branchwidth, and tangles! Oh my!
• Planar branch decompositions. I: The ratcatcher
• Planar branch decompositions. II: The cycle method
• Automata, Languages and Programming
• A local search algorithm for branchwidth

Describes a project that uses

Uses Software

• LEDA
• TSPLIB

This page was built for publication: Practical algorithms for branch-decompositions of planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896665)