Independent Set Reconfiguration in Cographs and their Generalizations
From MaRDI portal
Publication:2825488
DOI10.1002/jgt.21992zbMath1346.05209MaRDI QIDQ2825488
Publication date: 13 October 2016
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.21992
90C39: Dynamic programming
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
The Perfect Matching Reconfiguration Problem, Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect, Independent set reconfiguration parameterized by modular-width, On the complexity of distance-\(d\) independent set reconfiguration, Reconfiguration in bounded bandwidth and tree-depth, Reconfiguring graph homomorphisms on the sphere, Dominating sets reconfiguration under token sliding, On reconfigurability of target sets, Invitation to combinatorial reconfiguration, Reconfiguration of regular induced subgraphs, Parameterized complexity of independent set reconfiguration problems, Using contracted solution graphs for solving reconfiguration problems, Introduction to reconfiguration, Rerouting shortest paths in planar graphs, Reconfiguration of cliques in a graph
Cites Work
- Motion planning with pulley, rope, and baskets
- The complexity of rerouting shortest paths
- Complexity of independent set reconfigurability problems
- Approximability of the subset sum reconfiguration problem
- On the parameterized complexity of reconfiguration problems
- On the complexity of reconfiguration problems
- Shortest paths between shortest paths
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Upper bounds to the clique width of graphs
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- Connectedness of the graph of vertex-colourings
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of change
- Finding paths between 3-colorings
- Reconfiguring Independent Sets in Claw-Free Graphs
- A Linear Recognition Algorithm for Cographs
- Even-hole-free graphs: A survey
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
