Dynamic programming and planarity: improved tree-decomposition based algorithms
From MaRDI portal
Publication:972340
DOI10.1016/j.dam.2009.10.011zbMath1190.90258OpenAlexW1964495581MaRDI 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 programmingbranch-decompositionsplanar dominating setplanar graph TSPplanar Hamiltonian cycletree-decompositions
Trees (05C05) Dynamic programming (90C39) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
Four Shorts Stories on Surprising Algorithmic Uses of Treewidth, Fixed-Parameter Tractability of Treewidth and Pathwidth, Finding Paths in Grids with Forbidden Transitions
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
