Dynamic programming and planarity: improved tree-decomposition based algorithms

DOI10.1016/J.DAM.2009.10.011zbMATH Open1190.90258OpenAlexW1964495581MaRDI QIDQ972340FDOQ972340

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

Recommendations

• Practical access to dynamic programming on tree decompositions
• Practical access to dynamic programming on tree decompositions
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• A dynamic programming algorithm for the tree mapping problem
• scientific article; zbMATH DE number 4060712
• scientific article; zbMATH DE number 2086260
• Optimal dynamic program for \(r\)-domination problems over tree decompositions
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Revisiting dynamic programming for finding optimal subtrees in trees

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)

Cites Work

• Graph minors. X: Obstructions to tree-decomposition
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A Separator Theorem for Planar Graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Minimal triangulations of graphs: a survey
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Title not available (Why is that?)
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Dynamic Programming and Fast Matrix Multiplication
• The Pathwidth and Treewidth of Cographs
• The Use of Linear Graphs in Gauss Elimination
• Counting clique trees and computing perfect elimination schemes in parallel
• Tour merging via branch-decomposition
• Power of Natural Semijoins
• Finding small simple cycle separators for 2-connected planar graphs
• Characterizations and algorithmic applications of chordal graph embeddings
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Chordal embeddings of planar graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
• Algorithms – ESA 2005
• Title not available (Why is that?)
• Title not available (Why is that?)
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm

Cited In (13)

• Title not available (Why is that?)
• Finding Paths in Grids with Forbidden Transitions
• Fixed-Parameter Tractability of Treewidth and Pathwidth
• Revisiting dynamic programming for finding optimal subtrees in trees
• Dynamic Programming and Fast Matrix Multiplication
• Dynamic Programming, Integral Polyhedra and Horn Clause Knowledge Base
• Algorithms – ESA 2005
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Improving TSP Tours Using Dynamic Programming over Tree Decompositions
• Four Shorts Stories on Surprising Algorithmic Uses of Treewidth
• How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
• The Fine Details of Fast Dynamic Programming over Tree Decompositions

This page was built for publication: Dynamic programming and planarity: improved tree-decomposition based algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972340)