Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs

DOI10.1137/1.9781611972887.15MaRDI QIDQ5233518zbMATH OpenOpenAlexFDO

Authors Zhengbing Bian, Qian-Ping Gu, Marjan Marzban, Yumi Yoshitake, Hisao Tamaki

Publication date 11 September 2019

Published in 2008 Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/d1eda0bd8f6e93a5badf92549ecdb88ba9af0df7

Mathematics Subject Classification ID

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) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Practical algorithms for branch-decompositions of planar graphs
• A linear time heuristic for the branch-decomposition of planar graphs
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Automata, Languages and Programming
• scientific article; zbMATH DE number 2079336
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• On the tree-width of planar graphs

Cited in

(8)

• Computational study on planar dominating set problem
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Planar branch decompositions. I: The ratcatcher
• Planar branch decompositions. II: The cycle method
• A local search algorithm for branchwidth
• New analysis and computational study for the planar connected dominating set problem
• A combinatorial optimization algorithm for solving the branchwidth problem
• Practical algorithms for branch-decompositions of planar graphs

This page was built for publication: Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs

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