The complexity of independent set reconfiguration on bipartite graphs

zbMATH Open1403.68169MaRDI QIDQ4607889FDOQ4607889

Authors: Daniel Lokshtanov, Amer E. Mouawad 

Publication date: 15 March 2018

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

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

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)

Cited In (23)

• Computing \(k\)-independent sets for regular bipartite graphs
• Token sliding on split graphs
• Token sliding on split graphs
• Independent set reconfiguration parameterized by modular-width
• 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
• Title not available (Why is that?)
• 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
• Distributed Reconfiguration of Maximal Independent Sets
• Complexity of Hamiltonian cycle 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)