The complexity of independent set reconfiguration on bipartite graphs

MaRDI QIDQ4607889zbMATH OpenFDO

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)

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

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)