The Complexity of Dominating Set Reconfiguration
DOI10.1007/978-3-319-21840-3_33zbMath1451.68131arXiv1503.00833OpenAlexW2582871424MaRDI QIDQ3449837
Hirotaka Ono, Arash Haddadan, Youcef Tebbal, Amer E. Mouawad, Takehiro Ito, Naomi Nishimura, Akira Suzuki
Publication date: 30 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1503.00833
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 (7)
Cites Work
- Unnamed Item
- Reconfiguration of dominating sets
- Complexity of independent set reconfigurability problems
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Dominating sets for split and bipartite graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- The \(k\)-dominating graph
- 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
- Reconfiguration of Vertex Covers in a Graph
- Graph Classes: A Survey
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: The Complexity of Dominating Set Reconfiguration
