On the complexity of distance-d independent set reconfiguration

DOI10.1016/J.TCS.2024.114682MaRDI QIDQ6589843zbMATH OpenFDO

Authors Duc A. Hoang

Publication date 20 August 2024

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

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114682

zbMATH Keywords

computational complexitydistance-\(d\) independent setreconfiguration problemtoken jumpingtoken sliding

Mathematics Subject Classification ID

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

Cites work

• Algorithms for Square Roots of Graphs
• Complexity of independent set reconfigurability problems
• Computing \(k\)-independent sets for regular bipartite graphs
• Distance-\(d\) independent set problems for bipartite and chordal graphs
• Extremal independent set reconfiguration
• Families of graphs closed under taking powers
• Games, puzzles, and computation
• Graph theory
• scientific article; zbMATH DE number 3834023 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 637355 (Why is no real title available?)
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• Improved (In-)approximability bounds for \(d\)-scattered set
• Independent set reconfiguration in cographs and their generalizations
• Independent set reconfiguration on directed graphs
• Introduction to reconfiguration
• Linear-time algorithm for sliding tokens on trees
• On distance-\(d\) Independent Set and other problems in graphs with ``few minimal separators
• On powers of chordal graphs and their colorings
• On reconfiguration graphs of independent sets under token sliding
• On the complexity of distance-\(d\) independent set reconfiguration
• On the complexity of reconfiguration problems
• Parameterized complexity of graph constraint logic
• Powers of geometric intersection graphs and dispersion algorithms
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration in bounded bandwidth and tree-depth
• Reconfiguration on nowhere dense graph classes
• Reconfiguring independent sets in claw-free graphs
• Reconfiguring Independent Sets on Interval Graphs
• Sliding token on bipartite permutation graphs
• Structurally parameterized \(d\)-scattered set
• The complexity of change
• The complexity of independent set reconfiguration on bipartite graphs
• The complexity of rerouting shortest paths
• The maximum distance-d independent set problem on unit disk graphs
• Token sliding on chordal graphs
• Token sliding on split graphs
• Tree Powers

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

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