The Fine Details of Fast Dynamic Programming over Tree Decompositions
From MaRDI portal
Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
- Practical access to dynamic programming on tree decompositions
- Practical access to dynamic programming on tree decompositions
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- Revisiting dynamic programming for finding optimal subtrees in trees
- DynASP2.5: Dynamic Programming on Tree Decompositions in Action
- Improving the efficiency of dynamic programming on tree decompositions via machine learning
- Nonserial Dynamic Programming and Tree Decomposition in Discrete Optimization
- scientific article; zbMATH DE number 4060712
- Tree Decompositions of Graphs: Saving Memory in Dynamic Programming
Cited in
(35)- Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
- Practical access to dynamic programming on tree decompositions
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- scientific article; zbMATH DE number 2086260 (Why is no real title available?)
- Solving the problem of finding an independent \(\{K_1,K_2\}\)-packing of maximum weight on graphs of bounded treewidth
- Using contracted solution graphs for solving reconfiguration problems
- Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
- Orthogonal planarity testing of bounded treewidth graphs
- Polynomial-time algorithms for \textsc{Path Cover} on trees and graphs of bounded treewidth
- Speeding up dynamic programming with representative sets: an experimental evaluation of algorithms for Steiner Tree on tree decompositions
- Revisiting dynamic programming for finding optimal subtrees in trees
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- Positive-instance driven dynamic programming for treewidth
- Space-efficient vertex separators for treewidth
- Practical access to dynamic programming on tree decompositions
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- Dynamic Programming and Fast Matrix Multiplication
- Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
- Composing dynamic programming tree-decomposition-based algorithms
- On the \(k\)-rainbow domination in graphs with bounded tree-width
- An efficient algorithm to compute the toughness in graphs with bounded treewidth
- Tree decompositions of graphs: saving memory in dynamic programming
- DynASP2.5: Dynamic Programming on Tree Decompositions in Action
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- Fast Algorithms for Join Operations on Tree Decompositions
- scientific article; zbMATH DE number 7651213 (Why is no real title available?)
- Space saving by dynamic algebraization
- Efficient problem solving on tree decompositions using binary decision diagrams
- Parameterized complexity of happy coloring problems
- Speeding up dynamic programming with representative sets. An experimental evaluation of algorithms for Steiner Tree on tree decompositions
- Sketched representations and orthogonal planarity of bounded treewidth graphs
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Optimal tree decompositions revisited: a simpler linear-time FPT algorithm
- Nonserial Dynamic Programming and Tree Decomposition in Discrete Optimization
- Improving the efficiency of dynamic programming on tree decompositions via machine learning
This page was built for publication: The Fine Details of Fast Dynamic Programming over Tree Decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867071)