Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
From MaRDI portal
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)
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
- 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?)
- 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
- 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
(47)- Graph classes with structured neighborhoods and algorithmic applications
- Mim-width. III. Graph powers and generalized distance domination problems
- Star colouring of bounded degree graphs and regular graphs
- A simple optimal algorithm for \(k\)-tuple dominating problem in interval graphs
- Node multiway cut and subset feedback vertex set on graphs of bounded mim-width
- Solving problems on generalized convex graphs via mim-width
- Generalized distance domination problems and their complexity on graphs of bounded mim-width
- Bounding the Mim-Width of Hereditary Graph Classes.
- Treewidth versus clique number. II: Tree-independence number
- Boolean-width of graphs
- On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs
- When an optimal dominating set with given constraints exists
- A new approach on locally checkable problems
- Faster algorithms for vertex partitioning problems parameterized by clique-width
- More applications of the \(d\)-neighbor equivalence: acyclicity and connectivity constraints
- Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
- Graph classes with structured neighborhoods and algorithmic applications
- List k-colouring P_t-free graphs: a mim-width perspective
- Composing dynamic programming tree-decomposition-based algorithms
- Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width
- Solving problems on generalized convex graphs via mim-width
- Fast exact algorithms for some connectivity problems parameterized by clique-width
- scientific article; zbMATH DE number 7378700 (Why is no real title available?)
- Maximum rooted connected expansion
- Cluster deletion on interval graphs and split related graphs
- Cluster deletion on interval graphs and split related graphs
- Finding perfect matching cuts faster
- Clique‐width: Harnessing the power of atoms
- \(b\)-coloring parameterized by clique-width
- Parameterized algorithms for Steiner tree and dominating set: bounding the leafage by the vertex leafage
- On the tractability of optimization problems on \(H\)-graphs
- The perfect matching cut problem revisited
- The perfect matching cut problem revisited
- Polynomial-time algorithms for the longest induced path and induced disjoint paths problems on graphs of bounded mim-width
- Classes of intersection digraphs with good algorithmic properties
- On \(d\)-stable locally checkable problems parameterized by mim-width
- Mim-width. I. Induced path problems
- An algorithmic framework for locally constrained homomorphisms
- Distance domination in graphs
- Domination and Cut Problems on Chordal Graphs with Bounded Leafage
- More results on weighted independent domination
- More applications of the \(d\)-neighbor equivalence: connectivity and acyclicity constraints
- On the complexity of finding large odd induced subgraphs and odd colorings
- Bounding the mim‐width of hereditary graph classes
- Approximation hardness of domination problems on generalized convex graphs
- New algorithms for weighted \(k\)-domination and total \(k\)-domination problems in proper interval graphs
- Revising Johnson's table for the 21st century
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)
