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

DOI10.1016/j.tcs.2024.114682MaRDI QIDQ6589843

Duc A. Hoang

Publication date: 20 August 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of rerouting shortest paths
• Complexity of independent set reconfigurability problems
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• The maximum distance-\(d\) independent set problem on unit disk graphs
• Powers of geometric intersection graphs and dispersion algorithms
• 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
• Improved (In-)approximability bounds for \(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
• On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators
• 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
• On the complexity of distance-\(d\) independent set reconfiguration
• On reconfiguration graphs of independent sets under token sliding
• Extremal independent set reconfiguration
• Reconfiguring Independent Sets on Interval Graphs
• Independent set reconfiguration on directed graphs

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