Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
From MaRDI portal
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Recommendations
- Graph classes with structured neighborhoods and algorithmic applications
- The Fine Details of Fast Dynamic Programming over Tree Decompositions
- Graph classes with structured neighborhoods and algorithmic applications
- On the Boolean-width of a graph: structure and applications
- scientific article; zbMATH DE number 4060712
Cites work
- Algorithms for Vertex Partitioning Problems on Partial k-Trees
- Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
- Boolean-width of graphs
- Finding good decompositions for dynamic programming on dense graphs
- Graph classes with structured neighborhoods and algorithmic applications
- scientific article; zbMATH DE number 3779513 (Why is no real title available?)
- scientific article; zbMATH DE number 1202982 (Why is no real title available?)
- scientific article; zbMATH DE number 1161563 (Why is no real title available?)
- scientific article; zbMATH DE number 921905 (Why is no real title available?)
- Linear time solvable optimization problems on graphs of bounded clique-width
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- On the Boolean-width of a graph: structure and applications
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
- Parametrized complexity theory.
- The complexity of satisfiability problems
Cited in
(62)- Maximum rooted connected expansion
- Cluster deletion on interval graphs and split related graphs
- Revising Johnson's table for the 21st century
- A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
- Star colouring of bounded degree graphs and regular graphs
- A new approach on locally checkable problems
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- Mim-width. I. Induced path problems
- On the tractability of optimization problems on \(H\)-graphs
- List k-colouring P_t-free graphs: a mim-width perspective
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- Mim-width. III. Graph powers and generalized distance domination problems
- More results on weighted independent domination
- When an optimal dominating set with given constraints exists
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- On algorithmic applications of sim-width and mim-width of (H₁,H₂)-free graphs
- Graph classes with structured neighborhoods and algorithmic applications
- Distance domination in graphs
- Boolean-width of graphs
- Graph classes with structured neighborhoods and algorithmic applications
- More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- On the tractability of optimization problems on \(H\)-graphs
- More applications of the d-neighbor equivalence: connectivity and acyclicity constraints
- Cluster deletion on interval graphs and split related graphs
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- On the complexity of finding large odd induced subgraphs and odd colorings
- The perfect matching cut problem revisited
- The perfect matching cut problem revisited
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- Bounding the mim‐width of hereditary graph classes
- Clique‐width: Harnessing the power of atoms
- Bounding the Mim-Width of Hereditary Graph Classes.
- Treewidth versus clique number. II: Tree-independence number
- Finding perfect matching cuts faster
- Solving problems on generalized convex graphs via mim-width
- Classes of intersection digraphs with good algorithmic properties
- On \(d\)-stable locally checkable problems parameterized by mim-width
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- An algorithmic framework for locally constrained homomorphisms
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Composing dynamic programming tree-decomposition-based algorithms
- \(b\)-coloring parameterized by clique-width
- Approximation hardness of domination problems on generalized convex graphs
- Hardness transitions of star colouring and restricted star colouring
- Finding induced subgraphs from graphs with small mim-width
- Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
- Tight complexity bounds for counting generalized dominating sets in bounded-treewidth graphs. I: Algorithmic results
- Odd cycle transversal on P₅-free graphs in polynomial time
- Domination and cut problems on chordal graphs with bounded leafage
- XNLP-completeness for parameterized problems on graphs with a linear structure
- On the hardness of generalized domination problems parameterized by mim-width
- Comparing width parameters on graph classes
- XNLP-completeness for parameterized problems on graphs with a linear structure
- Computing subset vertex covers in H-free graphs
- A survey on the parameterized complexity of reconfiguration problems
- Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard
- Residue domination in bounded-treewidth graphs
- On algorithmic applications of \(\mathcal{F}\)-branchwidth
- Solving problems on generalized convex graphs via mim-width
This page was built for publication: Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392025)
