Parameterized complexity of independent set reconfiguration problems
From MaRDI portal
Publication:2192091
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)
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 complexity of distance-\(d\) independent set reconfiguration
- Parameterized extension complexity of independent set and related problems
- On the parameterized complexity of reconfiguration of connected dominating sets
Cites work
- Complexity of independent set reconfigurability problems
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Fixed-parameter tractability of token jumping on planar graphs
- Games, puzzles, and computation
- Independent set reconfiguration in cographs and their generalizations
- Introduction to reconfiguration
- Linear-time algorithm for sliding tokens on trees
- On the Parameterized Complexity for Token Jumping on Graphs
- On the complexity of reconfiguration problems
- 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 over tree decompositions
- Reconfiguring independent sets in claw-free graphs
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
- Sliding token on bipartite permutation graphs
- Sliding tokens on a cactus
- The complexity of change
- The complexity of independent set reconfiguration on bipartite graphs
- Token jumping in minor-closed classes
- Token sliding on chordal graphs
Cited in
(15)- Independent-set reconfiguration thresholds of hereditary graph classes
- Independent-set reconfiguration thresholds of hereditary graph classes
- Incremental optimization of independent sets under the reconfiguration framework
- Fixed-parameter tractability of token jumping on planar graphs
- On finding short reconfiguration sequences between independent sets
- Reconfiguration of regular induced subgraphs
- On reconfiguration graphs of independent sets under token sliding
- On girth and the parameterized complexity of token sliding and token jumping
- Complexity of independent set reconfigurability problems
- The complexity of induced tree reconfiguration problems
- The complexity of independent set reconfiguration on bipartite graphs
- Extremal independent set reconfiguration
- The complexity of independent set reconfiguration on bipartite graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- On finding short reconfiguration sequences between independent sets
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)