Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in O(n^1+) time

DOI10.1016/J.TCS.2010.07.017MaRDI QIDQ553343zbMATH OpenOpenAlexFDO

Authors Qian-Ping Gu, Hisao Tamaki

Publication date 27 July 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.07.017

zbMATH Keywords

graph algorithmsgraph minorsbranch-decompositions

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph minors (05C83)

Recommendations

• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Improved bounds on the planar branchwidth with respect to the largest grid minor size

Cites work

• scientific article; zbMATH DE number 5764900 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A linear time heuristic for the branch-decomposition of planar graphs
• A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
• Approximation algorithms for treewidth
• Call routing and the ratcatcher
• Complexity of Finding Embeddings in a k-Tree
• Computing the branchwidth of interval graphs
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
• Constructive linear time algorithms for branchwidth
• Easy problems for tree-decomposable graphs
• Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. X: Obstructions to tree-decomposition
• Graph minors. XIII: The disjoint paths problem
• Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Quickly excluding a planar graph
• Tree-width and large grid minors in planar graphs
• Treewidth lower bounds with brambles

Cited in

(8)

• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Approximate tree decompositions of planar graphs in linear time
• Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
• Approximation algorithms for Euler genus and related problems
• New analysis and computational study for the planar connected dominating set problem
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time

This page was built for publication: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time

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