On the complexity of distance-\(d\) independent set reconfiguration

DOI10.1007/978-3-031-27051-2_22arXiv2208.07199OpenAlexW4324009844MaRDI QIDQ6091168

Duc A. Hoang

Publication date: 24 November 2023

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityreconfiguration problemdistance-\(d\) independent settoken slidingtoken jumping

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of independent set reconfigurability problems
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• Reconfiguration on nowhere dense graph classes
• Reconfiguration in bounded bandwidth and tree-depth
• Token sliding on chordal graphs
• Reconfiguration on sparse graphs
• Token sliding on split graphs
• Structurally parameterized \(d\)-scattered set
• Introduction to reconfiguration
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Independent Set Reconfiguration in Cographs and their Generalizations
• Graph Theory
• The complexity of change
• Reconfiguring Independent Sets in Claw-Free Graphs
• Sliding Token on Bipartite Permutation Graphs
• Tree Powers
• The Complexity of Independent Set Reconfiguration on Bipartite Graphs
• Algorithms for Square Roots of Graphs
• Parameterized Complexity of Graph Constraint Logic
• Families of graphs closed under taking powers
• Reconfiguring Independent Sets on Interval Graphs

This page was built for publication: On the complexity of distance-\(d\) independent set reconfiguration