Dynamic programming and planarity: improved tree-decomposition based algorithms

DOI10.1016/j.dam.2009.10.011zbMath1190.90258OpenAlexW1964495581MaRDI QIDQ972340

Frederic Dorn

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

zbMATH Keywords

dynamic programmingbranch-decompositionsplanar dominating setplanar graph TSPplanar Hamiltonian cycletree-decompositions

Mathematics Subject Classification ID

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