The complexity of dominating set reconfiguration

DOI10.1016/j.tcs.2016.08.016zbMath1359.68133OpenAlexW1484691446MaRDI QIDQ517018

Hirotaka Ono, Arash Haddadan, Youcef Tebbal, Akira Suzuki, Amer E. Mouawad, Naomi Nishimura, Takehiro Ito

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2016.08.016

zbMATH Keywords

graph algorithmdominating setcombinatorial reconfiguration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (22)

Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Irredundance trees of diameter 3 ⋮ Fixed-parameter algorithms for graph constraint logic ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Cut-colorings in coloring graphs ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ Linear transformations between dominating sets in the TAR-model ⋮ On k-Total Dominating Graphs ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Dominating sets reconfiguration under token sliding ⋮ Reconfiguring Minimum Dominating Sets in Trees ⋮ Reconfiguring dominating sets in minor-closed graph classes ⋮ Reconfiguration graphs for dominating sets ⋮ Irredundance graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets

Cites Work

• Unnamed Item
• Reconfiguration of dominating sets
• Complexity of independent set reconfigurability problems
• Linear-time algorithm for sliding tokens on trees
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
• Dominating sets for split and bipartite graphs
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• The \(k\)-dominating graph
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• Vertex Cover Reconfiguration and Beyond
• Independent Set Reconfiguration in Cographs
• Reconfiguration of Cliques in a Graph
• Finding paths between 3-colorings
• Reconfiguring Independent Sets in Claw-Free Graphs
• Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
• The Complexity of Dominating Set Reconfiguration
• Graph Classes: A Survey
• Parameterized Complexity of Graph Constraint Logic
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

This page was built for publication: The complexity of dominating set reconfiguration