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

DOI10.1016/J.TCS.2010.07.017zbMATH Open1217.68246OpenAlexW2059590924MaRDI QIDQ553343FDOQ553343

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

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

zbMATH Keywords

graph algorithmsgraph minorsbranch-decompositions

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• 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
• Improved bounds on the planar branchwidth with respect to the largest grid minor size

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)