Approximate tree decompositions of planar graphs in linear time
From MaRDI portal
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)
Recommendations
Cites work
- scientific article; zbMATH DE number 176761 (Why is no real title available?)
- scientific article; zbMATH DE number 176762 (Why is no real title available?)
- scientific article; zbMATH DE number 566078 (Why is no real title available?)
- scientific article; zbMATH DE number 1953101 (Why is no real title available?)
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A note on two problems in connexion with graphs
- A partial k-arboretum of graphs with bounded treewidth
- Approximate tree decompositions of planar graphs in linear time
- Approximation algorithms for treewidth
- Call routing and the ratcatcher
- Complexity of Finding Embeddings in a k-Tree
- Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
- Easy problems for tree-decomposable graphs
- Efficient Planarity Testing
- Graph minors. II. Algorithmic aspects of tree-width
- Graph minors. III. Planar tree-width
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XIII: The disjoint paths problem
- Improved Approximation Algorithms for Minimum Weight Vertex Separators
- Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
- Rank-width and tree-width of \(H\)-minor-free graphs
- Rank‐width is less than or equal to branch‐width
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
Cited in
(14)- On the tree-width of planar graphs
- Degree-constrained decompositions of graphs: Bounded treewidth and planarity
- On Computing the Hamiltonian Index of Graphs
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Large independent sets in subquartic planar graphs
- Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
- Treelength of series-parallel graphs
- Algorithms finding tree-decompositions of graphs
- Linear-time algorithms for problems on planar graphs with fixed disk dimension
- Approximate tree decompositions of planar graphs in linear time
- New analysis and computational study for the planar connected dominating set problem
- On computing the Hamiltonian index of graphs
- A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
- scientific article; zbMATH DE number 475595 (Why is no real title available?)
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)
