Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Recommendations
Cited in
(83)- Tight bounds for chordal/interval vertex deletion parameterized by treewidth
- On the optimality of pseudo-polynomial algorithms for integer programming
- Fast exact algorithm for \(L(2,1)\)-labeling of graphs
- On the optimality of pseudo-polynomial algorithms for integer programming
- Facility location problems: a parameterized view
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- On the parameterized complexity of \([1,j]\)-domination problems
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Clifford algebras meet tree decompositions
- scientific article; zbMATH DE number 2086260 (Why is no real title available?)
- Parameterized domination in circle graphs
- Grundy Distinguishes Treewidth from Pathwidth
- Breaking the linear-memory barrier in MPC: fast MIS on trees with strongly sublinear memory
- Finer tight bounds for coloring on clique-width
- Finer tight bounds for coloring on clique-width
- Courcelle's theorem -- a game-theoretic approach
- Parameterized complexity of generalized domination problems
- A generic convolution algorithm for join operations on tree decompositions
- Boolean-width of graphs
- An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Graph minors and parameterized algorithm design
- Revisiting dynamic programming for finding optimal subtrees in trees
- Domination cover number of graphs
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- Counting problems in parameterized complexity
- Fast exact algorithm for L(2,1)-labeling of graphs
- On the Boolean-width of a graph: structure and applications
- Finding good decompositions for dynamic programming on dense graphs
- Efficient computation of permanents, with applications to boson sampling and random matrices
- Fine-grained complexity of the graph homomorphism problem for bounded-treewidth graphs
- The complexity of finding harmless individuals in social networks
- Complexity of fall coloring for restricted graph classes
- Parameterized complexity of paired domination
- Composing dynamic programming tree-decomposition-based algorithms
- Incremental and Efficient Computation of Families of Component Trees
- Boolean-width of graphs
- Parameterized complexity of modular dominating structures in bounded-treewidth graphs
- Maximum matching width: new characterizations and a fast algorithm for dominating set
- Computing generalized convolutions faster than brute force
- Algebraic decompositions of DP problems with linear dynamics
- On the maximum weight minimal separator
- New analysis and computational study for the planar connected dominating set problem
- Finding Hamiltonian cycle in graphs of bounded tree-width: experimental evaluation
- Degrees and gaps: tight complexity results of general factor problems parameterized by treewidth and cutwidth
- Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
- Confronting intractability via parameters
- DynASP2.5: Dynamic Programming on Tree Decompositions in Action
- On the Parameterized Complexity of [1,j]-Domination Problems
- scientific article; zbMATH DE number 7228418 (Why is no real title available?)
- Characterizing graphs of maximum matching width at most 2
- Grundy distinguishes treewidth from pathwidth
- 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
- Seeing Arboretum for the (partial k-) Trees
- Towards tight bounds for the graph homomorphism problem parameterized by cutwidth via asymptotic matrix parameters
- Fundamental problems on bounded-treewidth graphs: the real source of hardness
- Clifford algebras meet tree decompositions
- On the parameterized complexity of monotone and antimonotone weighted circuit satisfiability
- NP-completeness results for partitioning a graph into total dominating sets
- On the maximum weight minimal separator
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- Space saving by dynamic algebraization based on tree-depth
- Finding Hamiltonian cycle in graphs of bounded treewidth. Experimental evaluation
- Structurally parameterized \(d\)-scattered set
- On the equivalence among problems of bounded width
- Linear kernels for \(k\)-tuple and liar's domination in bounded genus graphs
- Algorithms for minimum membership dominating set problem
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- On the max min vertex cover problem
- Lower bounds for dynamic programming on planar graphs of bounded cutwidth
- A faster parameterized algorithm for pseudoforest deletion
- Faster algorithms on branch and clique decompositions
- scientific article; zbMATH DE number 7278055 (Why is no real title available?)
- Structural parameters, tight bounds, and approximation for \((k, r)\)-center
- Computing generalized convolutions faster than brute force
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
- Sidestepping barriers for dominating set in parameterized complexity
- On the Complexity of Bounded Context Switching.
- Inclusion/exclusion meets measure and conquer
- An efficient tree decomposition method for permanents and mixed discriminants
- Fixed-parameter tractability of treewidth and pathwidth
This page was built for publication: Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3639275)
