Complexity of independent set reconfigurability problems
From MaRDI portal
Publication:441866
DOI10.1016/J.TCS.2012.03.004zbMATH Open1246.05121OpenAlexW2145799305MaRDI QIDQ441866FDOQ441866
Authors: Paul Medvedev, Martin Milanič, Marcin Kamiński 
Publication date: 8 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.004
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
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)
Cites Work
- Normal hypergraphs and the perfect graph conjecture
- Complement reducible graphs
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Mixing 3-colourings in bipartite graphs
- Connectedness of the graph of vertex-colourings
- A Linear Recognition Algorithm for Cographs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Reconfiguration of List Edge-Colorings in a Graph
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- On the complexity of reconfiguration problems
- Shortest paths between shortest paths
- Shortest Paths between Shortest Paths and Independent Sets
- Even-hole-free graphs. I: Decomposition theorem
- Finding paths between 3-colourings
- Even-hole-free graphs part II: Recognition algorithm
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
Cited In (73)
- The complexity of rerouting shortest paths
- Reconfiguration of vertex covers in a graph
- Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
- Independent set reconfiguration in cographs and their generalizations
- On girth and the parameterized complexity of token sliding and token jumping
- Using contracted solution graphs for solving reconfiguration problems
- Feedback vertex set reconfiguration in planar graphs
- On reconfiguration graphs of independent sets under token sliding
- Token sliding on split graphs
- Token sliding on split graphs
- On reconfigurability of target sets
- ZDD-based algorithmic framework for solving shortest reconfiguration problems
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Reconfiguration on nowhere dense graph classes
- A reconfigurations analogue of Brooks' theorem and its consequences
- Homomorphism reconfiguration via homotopy
- Independent-set reconfiguration thresholds of hereditary graph classes
- Token sliding on graphs of girth five
- Parameterized complexity of independent set reconfiguration problems
- Finding shortest paths between graph colourings
- Finding shortest paths between graph colourings
- Reconfiguration in bounded bandwidth and tree-depth
- Shortest reconfiguration paths in the solution space of Boolean formulas
- Introduction to reconfiguration
- Reconfiguration of cliques in a graph
- Dominating sets reconfiguration under token sliding
- Invitation to combinatorial reconfiguration
- Reconfiguration of regular induced subgraphs
- Sliding tokens on block graphs
- On the complexity of distance-\(d\) independent set reconfiguration
- The complexity of independent set reconfiguration on bipartite graphs
- On reconfiguration graphs: an abstraction
- Title not available (Why is that?)
- Independent set reconfiguration in cographs
- Inapproximability of shortest paths on perfect matching polytopes
- Approximability of the subset sum reconfiguration problem
- The complexity of dominating set reconfiguration
- Reconfiguration of colorable sets in classes of perfect graphs
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Vertex Cover Reconfiguration and Beyond
- Fixed-parameter algorithms for graph constraint logic
- Fixed-parameter algorithms for graph constraint logic
- Linear-time algorithm for sliding tokens on trees
- The complexity of induced tree reconfiguration problems
- Distributed reconfiguration of maximal independent sets
- Reconfiguration of Colorable Sets in Classes of Perfect Graphs
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- Reconfiguration of graph minors
- Computational complexity of puzzles and related topics
- Reconfiguration of cliques in a graph
- Reconfiguration of maximum-weight \(b\)-matchings in a graph
- The complexity of dominating set reconfiguration
- The complexity of independent set reconfiguration on bipartite graphs
- Computational complexity of jumping block puzzles
- The Perfect Matching Reconfiguration Problem
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
- Reconfiguration of Steiner trees in an unweighted graph
- Induced paths in graphs without anticomplete cycles
- Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
- On the complexity of distance-\(d\) independent set reconfiguration
- Shortest reconfiguration of perfect matchings via alternating cycles
- Token sliding on graphs of girth five
- On finding short reconfiguration sequences between independent sets
- Computational complexity of jumping block puzzles
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- Transportation Problem Allowing Sending and Bringing Back
- Galactic token sliding
- Incremental optimization of independent sets under the reconfiguration framework
- Title not available (Why is that?)
- Hamiltonian cycle reconfiguration with answer set programming
- Recongo: bounded combinatorial reconfiguration with answer set programming
- Distributed Reconfiguration of Maximal Independent Sets
- Extremal independent set reconfiguration
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)
