Complexity of independent set reconfigurability problems
From MaRDI portal
Recommendations
- The complexity of independent set reconfiguration on bipartite graphs
- The complexity of independent set reconfiguration on bipartite graphs
- Parameterized complexity of independent set reconfiguration problems
- Independent set reconfiguration in cographs
- Shortest Paths between Shortest Paths and Independent Sets
Cites work
- A Linear Recognition Algorithm for Cographs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Complement reducible graphs
- Connectedness of the graph of vertex-colourings
- Even-hole-free graphs part II: Recognition algorithm
- Even-hole-free graphs. I: Decomposition theorem
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
- Finding paths between 3-colourings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Normal hypergraphs and the perfect graph conjecture
- On the complexity of reconfiguration problems
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Reconfiguration of List Edge-Colorings in a Graph
- Relationships between nondeterministic and deterministic tape complexities
- Shortest Paths between Shortest Paths and Independent Sets
- Shortest paths between shortest paths
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Cited in
(73)- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- Incremental optimization of independent sets under the reconfiguration framework
- Transportation Problem Allowing Sending and Bringing Back
- Hamiltonian cycle reconfiguration with answer set programming
- Recongo: bounded combinatorial reconfiguration with answer set programming
- Shortest reconfiguration of perfect matchings via alternating cycles
- scientific article; zbMATH DE number 7525498 (Why is no real title available?)
- Induced paths in graphs without anticomplete cycles
- Distributed Reconfiguration of Maximal Independent Sets
- Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
- On the complexity of distance-\(d\) independent set reconfiguration
- Computational complexity of jumping block puzzles
- Extremal independent set reconfiguration
- Galactic token sliding
- On finding short reconfiguration sequences between independent sets
- Token sliding on graphs of girth five
- Distributed reconfiguration of maximal independent sets
- Reconfiguration of graph minors
- A reconfigurations analogue of Brooks' theorem and its consequences
- Independent-set reconfiguration thresholds of hereditary graph classes
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- Linear-time algorithm for sliding tokens on trees
- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- The complexity of rerouting shortest paths
- Reconfiguration of cliques in a graph
- Using contracted solution graphs for solving reconfiguration problems
- Parameterized complexity of independent set reconfiguration problems
- Dominating sets reconfiguration under token sliding
- Feedback vertex set reconfiguration in planar graphs
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
- The Perfect Matching Reconfiguration Problem
- Reconfiguration in bounded bandwidth and tree-depth
- Reconfiguration of vertex covers in a graph
- Inapproximability of shortest paths on perfect matching polytopes
- Reconfiguration on nowhere dense graph classes
- On reconfiguration graphs: an abstraction
- Reconfiguration of maximum-weight \(b\)-matchings in a graph
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Invitation to combinatorial reconfiguration
- Reconfiguration of regular induced subgraphs
- On reconfiguration graphs of independent sets under token sliding
- On reconfigurability of target sets
- Token sliding on split graphs
- Approximability of the subset sum reconfiguration problem
- Sliding tokens on block graphs
- Finding shortest paths between graph colourings
- Token sliding on split graphs
- Reconfiguration of colorable sets in classes of perfect graphs
- The complexity of dominating set reconfiguration
- On girth and the parameterized complexity of token sliding and token jumping
- Finding shortest paths between graph colourings
- ZDD-based algorithmic framework for solving shortest reconfiguration problems
- Computational complexity of puzzles and related topics
- Reconfiguration of cliques in a graph
- The complexity of induced tree reconfiguration problems
- The complexity of dominating set reconfiguration
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- The complexity of independent set reconfiguration on bipartite graphs
- Introduction to reconfiguration
- Independent set reconfiguration in cographs
- Vertex Cover Reconfiguration and Beyond
- Homomorphism reconfiguration via homotopy
- Shortest reconfiguration paths in the solution space of Boolean formulas
- The complexity of independent set reconfiguration on bipartite graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguration of Steiner trees in an unweighted graph
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- Independent set reconfiguration in cographs and their generalizations
- Fixed-parameter algorithms for graph constraint logic
- Fixed-parameter algorithms for graph constraint logic
- scientific article; zbMATH DE number 7765402 (Why is no real title available?)
- Computational complexity of jumping block puzzles
- Token sliding on graphs of girth five
This page was built for publication: Complexity of independent set reconfigurability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q441866)
