Parameterized complexity of independent set reconfiguration problems
DOI10.1016/J.DAM.2020.01.022zbMATH Open1442.05156OpenAlexW3008568895MaRDI QIDQ2192091FDOQ2192091
Authors: Takehiro Ito, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka, Marcin Kamiński 
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
Recommendations
- Complexity of independent set reconfigurability problems
- The complexity of independent set reconfiguration on bipartite graphs
- The complexity of independent set reconfiguration on bipartite graphs
- On the parameterized complexity of reconfiguration problems
- On the parameterized complexity of reconfiguration problems
- On the complexity of distance-\(d\) independent set reconfiguration
- Parameterized extension complexity of independent set and related problems
- Independent set reconfiguration parameterized by modular-width
- Independent set reconfiguration parameterized by modular-width
- On the parameterized complexity of reconfiguration of connected dominating sets
Graph algorithms (graph-theoretic aspects) (05C85) Dynamic programming (90C39) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of change
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Reconfiguring independent sets in claw-free graphs
- Games, puzzles, and computation
- Complexity of independent set reconfigurability problems
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Reconfiguration on sparse graphs
- Fixed-parameter tractability of token jumping on planar graphs
- On the Parameterized Complexity for Token Jumping on Graphs
- Token sliding on chordal graphs
- Reconfiguration over tree decompositions
- Linear-time algorithm for sliding tokens on trees
- Sliding token on bipartite permutation graphs
- Introduction to reconfiguration
- Reconfiguration in bounded bandwidth and tree-depth
- Token jumping in minor-closed classes
- The complexity of independent set reconfiguration on bipartite graphs
- Independent set reconfiguration in cographs and their generalizations
- Sliding tokens on a cactus
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
Cited In (16)
- Fixed-parameter tractability of token jumping on planar graphs
- On girth and the parameterized complexity of token sliding and token jumping
- On reconfiguration graphs of independent sets under token sliding
- Independent set reconfiguration parameterized by modular-width
- Independent-set reconfiguration thresholds of hereditary graph classes
- Independent-set reconfiguration thresholds of hereditary graph classes
- Complexity of independent set reconfigurability problems
- On the parameterized complexity of reconfiguration problems
- On finding short reconfiguration sequences between independent sets
- Reconfiguration of regular induced subgraphs
- On the complexity of distance-\(d\) independent set reconfiguration
- The complexity of independent set reconfiguration on bipartite graphs
- The complexity of induced tree reconfiguration problems
- Incremental optimization of independent sets under the reconfiguration framework
- The complexity of independent set reconfiguration on bipartite graphs
- Extremal independent set reconfiguration
This page was built for publication: Parameterized complexity of independent set reconfiguration problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2192091)
