Parameterized complexity of independent set reconfiguration problems
DOI10.1016/j.dam.2020.01.022zbMath1442.05156OpenAlexW3008568895MaRDI QIDQ2192091
Akira Suzuki, Ryuhei Uehara, Takehiro Ito, Hirotaka Ono, Katsuhisa Yamanaka, Marcin Kaminski
Publication date: 29 June 2020
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2020.01.022
Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Complexity of independent set reconfigurability problems
- Linear-time algorithm for sliding tokens on trees
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Token jumping in minor-closed classes
- Reconfiguration in bounded bandwidth and tree-depth
- 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
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
- Independent Set Reconfiguration in Cographs and their Generalizations
- The complexity of change
- Fixed-Parameter Tractability of Token Jumping on Planar Graphs
- Reconfiguration over Tree Decompositions
- Reconfiguring Independent Sets in Claw-Free Graphs
- Sliding Token on Bipartite Permutation Graphs
- Sliding Tokens on a Cactus
- On the Parameterized Complexity for Token Jumping on Graphs
This page was built for publication: Parameterized complexity of independent set reconfiguration problems
