The complexity of independent set reconfiguration on bipartite graphs

MaRDI QIDQ4607889zbMATHFDO

Authors Daniel Lokshtanov, Amer E. Mouawad

Publication date 15 March 2018

Full work available at URL http://dl.acm.org/citation.cfm?id=3175279

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• The complexity of independent set reconfiguration on bipartite graphs
• Complexity of independent set reconfigurability problems
• Parameterized complexity of independent set reconfiguration problems
• Token sliding on split graphs
• Independent set reconfiguration in cographs

Cited in

(22)

• Distributed reconfiguration of maximal independent sets
• Reconfiguring shortest paths in graphs
• Independent-set reconfiguration thresholds of hereditary graph classes
• TS-reconfiguration of dominating sets in circle and circular-arc graphs
• Reconfiguration of Colorable Sets in Classes of Perfect Graphs
• Incremental optimization of independent sets under the reconfiguration framework
• Parameterized complexity of independent set reconfiguration problems
• Dominating sets reconfiguration under token sliding
• Reconfiguration on nowhere dense graph classes
• scientific article; zbMATH DE number 7525461 (Why is no real title available?)
• Computing \(k\)-independent sets for regular bipartite graphs
• Distributed Reconfiguration of Maximal Independent Sets
• Token sliding on split graphs
• Reconfiguring Independent Sets on Interval Graphs
• Complexity of Hamiltonian cycle reconfiguration
• Token sliding on split graphs
• Reconfiguration of colorable sets in classes of perfect graphs
• Complexity of independent set reconfigurability problems
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• The complexity of independent set reconfiguration on bipartite graphs
• Introduction to reconfiguration
• On the complexity of distance-\(d\) independent set reconfiguration

This page was built for publication: The complexity of independent set reconfiguration on bipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607889)