Independent set reconfiguration in cographs and their generalizations

DOI10.1002/JGT.21992MaRDI QIDQ2825488zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dynamic programminggraph classesgraph decompositionefficient algorithmreconfiguration

Mathematics Subject Classification ID

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)

Recommendations

• Independent set reconfiguration in cographs
• Complexity of independent set reconfigurability problems
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• Extremal independent set reconfiguration
• Reconfiguration of colorable sets in classes of perfect graphs

Cites work

• A Linear Recognition Algorithm for Cographs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Approximability of the subset sum reconfiguration problem
• Complexity of independent set reconfigurability problems
• Connectedness of the graph of vertex-colourings
• Even-hole-free graphs: A survey
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Motion planning with pulley, rope, and baskets
• On maximal independent sets of vertices in claw-free 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 graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguring independent sets in claw-free graphs
• Shortest paths between shortest paths
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• The complexity of change
• The complexity of rerouting shortest paths
• Upper bounds to the clique width of graphs

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
• Independent set reconfiguration in cographs
• Reconfiguring independent sets in claw-free graphs
• 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)