Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time

DOI10.1007/978-3-642-10631-6_99zbMath1272.05200OpenAlexW2170677738MaRDI QIDQ3652285

Qian-Ping Gu, Hisao Tamaki

Publication date: 17 December 2009

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-10631-6_99

zbMATH Keywords

graph algorithmsconstant-factor approximation algorithmslargest grid graph minorsoptimal branch-decompositions

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (7)

Fast minor testing in planar graphs ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs ⋮ Induced packing of odd cycles in planar graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time