Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
From MaRDI portal
Publication:553343
DOI10.1016/j.tcs.2010.07.017zbMath1217.68246MaRDI QIDQ553343
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
05C83: Graph minors
05C85: Graph algorithms (graph-theoretic aspects)
68W25: Approximation algorithms
Related Items
Approximation Algorithms for Euler Genus and Related Problems, Deciding whether a grid is a topological subgraph of a planar graph is NP-complete, Approximate tree decompositions of planar graphs in linear time, New analysis and computational study for the planar connected dominating set problem, Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs, Improved bounds on the planar branchwidth with respect to the largest grid minor size
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
- Approximation algorithms for treewidth
- Treewidth lower bounds with brambles
- Graph minors. I. Excluding a forest
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Quickly excluding a planar graph
- Computing the branchwidth of interval graphs
- Graph minors. XIII: The disjoint paths problem
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
- Easy problems for tree-decomposable graphs
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity of Finding Embeddings in a k-Tree
- Constructive linear time algorithms for branchwidth
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Algorithms - ESA 2003
