Extremal independent set reconfiguration
From MaRDI portal
Publication:6133144
DOI10.37236/11771zbMath1519.05188arXiv2301.02020OpenAlexW4385358738MaRDI QIDQ6133144
Théo Pierron, Nicolas Bousquet, Steéphan Thomassé, Bastien Durain
Publication date: 18 August 2023
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2301.02020
Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of independent set reconfigurability problems
- Linear-time algorithm for sliding tokens on trees
- Shortest paths between shortest paths
- Reconfiguration in bounded bandwidth and tree-depth
- Token sliding on chordal graphs
- Introduction to reconfiguration
- Hypergraph regularity and the multidimensional Szemerédi theorem
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of change
- The Complexity of Independent Set Reconfiguration on Bipartite Graphs
- The hypergraph regularity method and its applications
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Generalizations of the Ruzsa–Szemerédi and rainbow Turán problems for cliques
- On reconfiguration graphs of independent sets under token sliding
This page was built for publication: Extremal independent set reconfiguration
