Independent set reconfiguration in cographs and their generalizations
DOI10.1002/JGT.21992zbMATH Open1346.05209OpenAlexW2176718028MaRDI QIDQ2825488FDOQ2825488
Authors: Paul Bonsma 
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
Recommendations
Dynamic programming (90C39) 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
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Upper bounds to the clique width of graphs
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Mixing 3-colourings in bipartite graphs
- On maximal independent sets of vertices in claw-free graphs
- Connectedness of the graph of vertex-colourings
- The complexity of change
- Finding paths between 3-colorings
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- A Linear Recognition Algorithm for Cographs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- Reconfiguring independent sets in claw-free graphs
- Complexity of independent set reconfigurability problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- On the complexity of reconfiguration problems
- Shortest paths between shortest paths
- Motion planning with pulley, rope, and baskets
- The complexity of rerouting shortest paths
- Even-hole-free graphs: A survey
- Approximability of the subset sum reconfiguration problem
Cited In (17)
- Reconfiguring graph homomorphisms on the sphere
- Using contracted solution graphs for solving reconfiguration problems
- Rerouting shortest paths in planar graphs
- On reconfigurability of target sets
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguring Independent Sets on Interval Graphs
- Parameterized complexity of independent set reconfiguration problems
- Reconfiguration in bounded bandwidth and tree-depth
- Introduction to reconfiguration
- Dominating sets reconfiguration under token sliding
- Invitation to combinatorial reconfiguration
- Reconfiguration of regular induced subgraphs
- On the complexity of distance-\(d\) independent set reconfiguration
- Reconfiguring independent sets in claw-free graphs
- Independent set reconfiguration in cographs
- Reconfiguration of cliques in a graph
- The Perfect Matching Reconfiguration Problem
This page was built for publication: Independent set reconfiguration in cographs and their generalizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2825488)
