Decremental Optimization of Dominating Sets Under the Reconfiguration Framework

DOI10.1007/978-3-030-48966-3_6MaRDI QIDQ5041181zbMATH OpenOpenAlexFDO

Authors Alexandre Blanché, Haruka Mizuta, Paul Ouvrard, Akira Suzuki

Publication date 13 October 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1906.05163

zbMATH Keywords

combinatorial reconfigurationdominating setparameterized complexity

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Recommendations

• Decremental optimization of vertex-coloring under the reconfiguration framework
• The complexity of dominating set reconfiguration
• The complexity of dominating set reconfiguration
• On the parameterized complexity of reconfiguration of connected dominating sets
• scientific article; zbMATH DE number 7764115
• Incremental optimization of independent sets under the reconfiguration framework
• Incremental optimization of independent sets under the reconfiguration framework
• Reconfiguration graphs for dominating sets

Cites work

• Complexity of independent set reconfigurability problems
• Dominating sets for split and bipartite graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• Improved upper bounds for vertex cover
• Incremental optimization of independent sets under the reconfiguration framework
• Introduction to reconfiguration
• Kernelization and Sparseness: the case of Dominating Set
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• The complexity of change
• The complexity of dominating set reconfiguration
• The complexity of independent set reconfiguration on bipartite graphs
• Token sliding on chordal graphs
• Vertex Cover Reconfiguration and Beyond

Cited in

(5)

• Dominating sets reconfiguration under token sliding
• Decremental optimization of vertex-coloring under the reconfiguration framework
• Linear transformations between dominating sets in the TAR-model
• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• Gap preserving reductions between reconfiguration problems

This page was built for publication: Decremental Optimization of Dominating Sets Under the Reconfiguration Framework

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5041181)