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