Dynamic programming and planarity: improved tree-decomposition based algorithms
From MaRDI portal
Publication:972340
DOI10.1016/j.dam.2009.10.011zbMath1190.90258MaRDI QIDQ972340
Publication date: 25 May 2010
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2009.10.011
dynamic programming; branch-decompositions; planar dominating set; planar graph TSP; planar Hamiltonian cycle; tree-decompositions
05C05: Trees
90C39: Dynamic programming
05C10: Planar graphs; geometric and topological aspects of graph theory
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Related Items
Finding Paths in Grids with Forbidden Transitions, Fixed-Parameter Tractability of Treewidth and Pathwidth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Minimal triangulations of graphs: a survey
- Finding small simple cycle separators for 2-connected planar graphs
- Graph minors. X: Obstructions to tree-decomposition
- Counting clique trees and computing perfect elimination schemes in parallel
- Characterizations and algorithmic applications of chordal graph embeddings
- Chordal embeddings of planar graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Tour Merging via Branch-Decomposition
- The Use of Linear Graphs in Gauss Elimination
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm
- A Separator Theorem for Planar Graphs
- Power of Natural Semijoins
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Subgraph Isomorphism in Planar Graphs and Related Problems
- The Pathwidth and Treewidth of Cographs
- Dynamic Programming and Fast Matrix Multiplication
- Algorithms – ESA 2005
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
