Decremental Optimization of Dominating Sets Under the Reconfiguration Framework

DOI10.1007/978-3-030-48966-3_6OpenAlexW3030255139MaRDI QIDQ5041181

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

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

dominating setparameterized complexitycombinatorial reconfiguration

Mathematics Subject Classification ID

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

Related Items (4)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Reconfiguration of dominating sets
• Complexity of independent set reconfigurability problems
• The complexity of dominating set reconfiguration
• On the parameterized complexity of reconfiguration problems
• On the complexity of reconfiguration problems
• Improved upper bounds for vertex cover
• Dominating sets for split and bipartite graphs
• Linear time algorithms for finding a dominating set of fixed size in degenerated graphs
• Token sliding on chordal graphs
• Reconfiguration on sparse graphs
• Introduction to reconfiguration
• 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
• Kernelization and Sparseness: the case of Dominating Set
• The Complexity of Independent Set Reconfiguration on Bipartite Graphs
• Incremental optimization of independent sets under the reconfiguration framework

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