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
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Finding Paths in Grids with Forbidden Transitions, Fixed-Parameter Tractability of Treewidth and Pathwidth
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item