Approximate tree decompositions of planar graphs in linear time
DOI10.1016/J.TCS.2016.06.040zbMATH Open1348.68296OpenAlexW2475293459MaRDI QIDQ306256FDOQ306256
Publication date: 31 August 2016
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2016.06.040
Recommendations
- Approximate tree decompositions of planar graphs in linear time
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Algorithms finding tree-decompositions of graphs
- Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- A note on two problems in connexion with graphs
- Graph minors. X: Obstructions to tree-decomposition
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A partial k-arboretum of graphs with bounded 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
- Efficient Planarity Testing
- Title not available (Why is that?)
- Graph minors. II. Algorithmic aspects of tree-width
- Approximation algorithms for treewidth
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
- Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Rank‐width is less than or equal to branch‐width
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Title not available (Why is that?)
- Rank-width and tree-width of \(H\)-minor-free graphs
- Graph minors. III. Planar tree-width
Cited In (11)
- On computing the Hamiltonian index of graphs
- On Computing the Hamiltonian Index of Graphs
- Title not available (Why is that?)
- New analysis and computational study for the planar connected dominating set problem
- Algorithms finding tree-decompositions of graphs
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
- Large Independent Sets in Subquartic Planar Graphs
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Treelength of series-parallel graphs
This page was built for publication: Approximate tree decompositions of planar graphs in linear time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q306256)
