Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution

DOI10.1007/978-3-642-04128-0_51zbMath1256.68157OpenAlexW1579510955WikidataQ59567694 ScholiaQ59567694MaRDI QIDQ3639275

Johan M. M. van Rooij, Hans L. Bodlaender, Peter Rossmanith

Publication date: 29 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04128-0_51

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (63)

An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification ⋮ Finding Good Decompositions for Dynamic Programming on Dense Graphs ⋮ Seeing Arboretum for the (partial k-) Trees ⋮ Fast Algorithms for Join Operations on Tree Decompositions ⋮ Efficient computation of permanents, with applications to boson sampling and random matrices ⋮ On the Equivalence among Problems of Bounded Width ⋮ Unnamed Item ⋮ Fixed-Parameter Tractability of Treewidth and Pathwidth ⋮ Graph Minors and Parameterized Algorithm Design ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Unnamed Item ⋮ Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs ⋮ Space saving by dynamic algebraization based on tree-depth ⋮ On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability ⋮ Characterizing graphs of maximum matching width at most 2 ⋮ Maximum matching width: new characterizations and a fast algorithm for dominating set ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Fast exact algorithm for \(L(2,1)\)-labeling of graphs ⋮ Algebraic decompositions of DP problems with linear dynamics ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ A faster parameterized algorithm for pseudoforest deletion ⋮ Parameterized complexity of generalized domination problems ⋮ On the optimality of pseudo-polynomial algorithms for integer programming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing generalized convolutions faster than brute force ⋮ An efficient tree decomposition method for permanents and mixed discriminants ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized domination in circle graphs ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth ⋮ Confronting intractability via parameters ⋮ On the Maximum Weight Minimal Separator ⋮ Clifford algebras meet tree decompositions ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ Domination cover number of graphs ⋮ On the max min vertex cover problem ⋮ On the Optimality of Pseudo-polynomial Algorithms for Integer Programming ⋮ Fast Exact Algorithm for L(2,1)-Labeling of Graphs ⋮ Inclusion/exclusion meets measure and conquer ⋮ Facility location problems: a parameterized view ⋮ Boolean-width of graphs ⋮ On the Boolean-Width of a Graph: Structure and Applications ⋮ On the parameterized complexity of \([1,j\)-domination problems] ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ NP-completeness results for partitioning a graph into total dominating sets ⋮ An optimal XP algorithm for Hamiltonian cycle on graphs of bounded clique-width ⋮ Complexity of fall coloring for restricted graph classes ⋮ On the Parameterized Complexity of [1,j-Domination Problems] ⋮ Structurally parameterized \(d\)-scattered set ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth ⋮ Unnamed Item ⋮ Boolean-Width of Graphs ⋮ On the Complexity of Bounded Context Switching. ⋮ On the maximum weight minimal separator ⋮ The complexity of finding harmless individuals in social networks ⋮ Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs ⋮ Unnamed Item ⋮ Finding Hamiltonian Cycle in Graphs of Bounded Treewidth: Experimental Evaluation ⋮ A generic convolution algorithm for join operations on tree decompositions

This page was built for publication: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution