Shortest reconfiguration of sliding tokens on subclasses of interval graphs
DOI10.1016/J.TCS.2021.02.019zbMATH Open1497.68399OpenAlexW3129648991MaRDI QIDQ2658043FDOQ2658043
Authors: Takeshi Yamada, Ryuhei Uehara 
Publication date: 18 March 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.02.019
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62)
Cites Work
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Finding paths between 3-colorings
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- On the diameter of reconfiguration graphs for vertex colourings
- Reconfiguring Independent Sets in Claw-Free Graphs
- Games, puzzles, and computation
- Complexity of independent set reconfigurability problems
- On the parameterized complexity of reconfiguration problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- On the complexity of reconfiguration problems
- Shortest paths between shortest paths
- A short proof that `proper = unit'
- An exact algorithm for the Boolean connectivity problem for \(k\)-CNF
- Token sliding on chordal graphs
- Reconfiguration over Tree Decompositions
- Linear-time algorithm for sliding tokens on trees
- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas
- Parameterized Complexity of Graph Constraint Logic
- Sliding Token on Bipartite Permutation Graphs
- Title not available (Why is that?)
- Sliding Tokens on a Cactus
Cited In (6)
- Token sliding on split graphs
- On finding short reconfiguration sequences between independent sets
- Computational complexity of puzzles and related topics
- Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
- 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
- Shortest Reconfiguration of Sliding Tokens on a Caterpillar
This page was built for publication: Shortest reconfiguration of sliding tokens on subclasses of interval graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2658043)
