Independent Set Reconfiguration in Cographs and their Generalizations

DOI10.1002/jgt.21992zbMath1346.05209OpenAlexW2176718028MaRDI QIDQ2825488

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 decompositionefficient algorithmgraph classesreconfiguration

Mathematics Subject Classification ID

Dynamic programming (90C39) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (15)

Invitation to combinatorial reconfiguration ⋮ Reconfiguration of regular induced subgraphs ⋮ Rerouting shortest paths in planar graphs ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ Reconfiguration of cliques in a graph ⋮ Reconfiguring graph homomorphisms on the sphere ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Dominating sets reconfiguration under token sliding ⋮ Independent set reconfiguration parameterized by modular-width ⋮ The Perfect Matching Reconfiguration Problem ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ On reconfigurability of target sets

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

This page was built for publication: Independent Set Reconfiguration in Cographs and their Generalizations