The complexity of distance-r dominating set reconfiguration

DOI10.1007/978-981-96-1090-7_22MaRDI QIDQ6970724zbMATH OpenFDO

Authors Niranka Banerjee, Duc A. Hoang

Publication date 17 June 2025

Full work available at URL https://doi.org/10.1007/978-981-96-1090-7_22

zbMATH Keywords

computational complexitydistance-\(r\) dominating setpolynomial-time algorithmpspace-completenessreconfiguration problem

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Cites work

• Distance domination in graphs
• Dominating sets reconfiguration under token sliding
• Dually Chordal Graphs
• Graph theory
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• Introduction to reconfiguration
• On the complexity of reconfiguration problems
• On the parameterized complexity of reconfiguration problems
• Parameterized complexity of graph constraint logic
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration on nowhere dense graph classes
• Reconfiguration on sparse graphs
• Relations between packing and covering numbers of a tree
• Shortest Dominating Set Reconfiguration under Token Sliding
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• The complexity of change
• The complexity of dominating set reconfiguration
• TS-reconfiguration of dominating sets in circle and circular-arc graphs
• Which graphs occur as \(\gamma\)-graphs?

This page was built for publication: The complexity of distance-\(r\) dominating set reconfiguration

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