Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs

DOI10.1016/j.dam.2018.08.027zbMath1406.05102arXiv1407.6761MaRDI QIDQ1730234

Qian-Ping Gu, Gengchun Xu

Publication date: 11 March 2019

Published in: Discrete Applied Mathematics, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1407.6761

zbMATH Keywords

approximation algorithm; planar graphs; grid minor; branch-/tree-decompositions

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C10: Planar graphs; geometric and topological aspects of graph theory

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms