Fetching the paper…
Reading the bibliography…
Given a graph $G=(V,E)$ with $V=\{1,\ldots,n\}$, we place on every vertex a token $T_1,\ldots,T_n$.
Sorting and Searching
Donald E. Knuth · 1973
Earlier work this paper cites.
Graph puzzles, homotopy, and the alternating group
Richard M. Wilson · 1974
Earlier work this paper cites.
The complexity of finding minimum-length generator sequences
Mark R. Jerrum · 1985
Earlier work this paper cites.
The ( n 2 − 1 ) (n^{2}-1) -puzzle and related relocation problems
Daniel Ratner and Manfred Warmuth · 1990
Earlier work this paper cites.
Hardness of approximations
Sanjeev Arora and Carsten Lund · 1996
Earlier work this paper cites.
Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k k -ARY trees
Igor Pak · 1999
Earlier work this paper cites.
On the complexity of k k -SAT
Russell Impagliazzo and Ramamohan Paturi · 2000
Earlier work this paper cites.
Sorting by short swaps
Lenwood S. Heath and John Paul C. Vergara · 2003
Earlier work this paper cites.
PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
Robert A. Hearn and Erik D. Demaine · 2005
Cited alongside, same era.
Reconfigurations in graphs and grids
Gruia Călinescu, Adrian Dumitrescu, and János Pach · 2008
Cited alongside, same era.
The connectivity of Boolean satisfiability: Computational and structural dichotomies
Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, and Christos H. Papadimitriou · 2009
Cited alongside, same era.
Token graphs
Ruy Fabila-Monroy, David Flores-Peñaloza, Clemens Huemer, Ferran Hurtado, Jorge Urrutia, and David R. Wood · 2012
Cited alongside, same era.
Complexity of independent set reconfigurability problems
Marcin Kamiński, Paul Medvedev, and Martin Milanič · 2012
Cited alongside, same era.
Reconfiguring independent sets in claw-free graphs
Paul Bonsma, Marcin Kamiński, and Marcin Wrochna · 2014
Linear-time algorithm for sliding tokens on trees
Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada · 2015
Later among the works it cites.
Sliding token on bipartite permutation graphs
Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, and Ryuhei Uehara · 2015
Later among the works it cites.
How to sort by walking on a tree
Daniel Graf · 2015
Later among the works it cites.
Swapping labeled tokens on graphs
Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, and Takeaki Uno · 2015
Later among the works it cites.
Swapping colored tokens on graphs
Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, and Yushi Uno · 2015
Later among the works it cites.
Swapping labeled tokens on complete split graphs
Gaku Yasui, Kouta Abe, Katsuhisa Yamanaka, and Takashi Hirayama · 2015
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Reconfiguration over tree decompositions
Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, and Marcin Wrochna · 2014
Cited alongside, same era.
Invitation to combinatorial reconfiguration
Paul Bonsma, Takehiro Ito, Marcin Kamiński, and Naomi Nishimura · 2015
Cited alongside, same era.
Note on the theory of permutations
Arthur Cayley
Cited in the paper.
Later among the works it cites.
Complexity of token swapping and its variants
Édouard Bonnet, Tillmann Miltzow, and Paweł Rza̧żewski · 2016
Closest in time.
Approximation and hardness for token swapping
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, and Takeaki Uno · 2016
Closest in time.