Fetching the paper…
Reading the bibliography…
In the Token Swapping problem we are given a graph with a token placed on each vertex.
On a problem in formal logic
F. P. Ramsey · 1930
Earlier work this paper cites.
Relationships Between Nondeterministic and Deterministic Tape Complexities
W. J. Savitch · 1970
Earlier work this paper cites.
Graph puzzles, homotopy, and the alternating group
R. M. Wilson · 1974
Earlier work this paper cites.
Pursuit-evasion in a graph
T. D. Parsons · 1978
Earlier work this paper cites.
Classes of pebble games and complete problems
T. Kasai, A. Adachi, and S. Iwata · 1979
Earlier work this paper cites.
The NP-Completeness of the Hamiltonian Cycle Problem in Planar Digraphs with Degree Bound Two
J. Plesník · 1979
Earlier work this paper cites.
The NP-Completeness of Some Edge-Partition Problems
I. Holyer · 1981
Earlier work this paper cites.
Winning Ways, for Your Mathematical Plays: Games in particular
E. R. Berlekamp, J. H. Conway, and R. K. Guy · 1982
Earlier work this paper cites.
The Art of Computer Programming
D. E. Knuth · 1982
Earlier work this paper cites.
The complexity of completing partial latin squares
C. J. Colbourn · 1984
Earlier work this paper cites.
Clustering to minimize the maximum intercluster distance
T. F. Gonzalez · 1985
Earlier work this paper cites.
Classic Papers in Combinatorics
P. Erdős and G. Szekeres · 1987
Earlier work this paper cites.
Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ARY trees
I. Pak · 1999
Earlier work this paper cites.
Computational geometry
M. De Berg, M. Van Kreveld, M. Overmars, and O. C. Schwarzkopf · 2000
Cited alongside, same era.
On the complexity of k-sat
R. Impagliazzo and R. Paturi · 2001
Cited alongside, same era.
Which problems have strongly exponential complexity?
R. Impagliazzo, R. Paturi, and F. Zane · 2001
Cited alongside, same era.
Sorting by short swaps
L. S. Heath and J. P. C. Vergara · 2003
Cited alongside, same era.
Reconfigurations in graphs and grids
G. Calinescu, A. Dumitrescu, and J. Pach · 2006
Cited alongside, same era.
Flips in planar graphs
P. Bose and F. Hurtado · 2009
Cited alongside, same era.
A graphical model for computing the minimum cost transposition distance
F. Farnoud, C. Y. Chen, O. Milenkovic, and N. Kashyap · 2010
Deciding first-order properties of nowhere dense graphs
M. Grohe, S. Kreutzer, and S. Siebertz · 2014
Later among the works it cites.
Swapping labeled tokens on graphs
K. Yamanaka, E. D. Demaine, T. Ito, J. Kawahara, M. Kiyomi, Y. Okamoto, T. Saitoh, A. Suzuki, K. Uchizawa, and T. Uno · 2014
Later among the works it cites.
Subexponential time algorithms for finding small tree and path decompositions
H. L. Bodlaender and J. Nederlof · 2015
Later among the works it cites.
Linear-time algorithm for sliding tokens on trees
E. D. Demaine, M. L. Demaine, E. Fox-Epstein, D. A. Hoang, T. Ito, H. Ono, Y. Otachi, R. Uehara, and T. Yamada · 2015
Later among the works it cites.
Sliding token on bipartite permutation graphs
E. Fox-Epstein, D. A. Hoang, Y. Otachi, and R. Uehara · 2015
Later among the works it cites.
How to sort by walking on a tree
D. Graf · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Can you beat treewidth?
D. Marx · 2010
Cited alongside, same era.
Lower bounds based on the exponential time hypothesis
D. Lokshtanov, D. Marx, and S. Saurabh · 2011
Cited alongside, same era.
Token graphs
R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood · 2012
Cited alongside, same era.
Sorting of permutations by cost-constrained transpositions
F. Farnoud and O. Milenkovic · 2012
Cited alongside, same era.
Sparsity - Graphs, Structures, and Algorithms
J. Nešetřil and P. Ossona de Mendez · 2012
Cited alongside, same era.
Optimal parameterized algorithms for planar facility location problems using voronoi diagrams
D. Marx and M. Pilipczuk · 2015
Later among the works it cites.
Swapping colored tokens on graphs
K. Yamanaka, T. Horiyama, D. G. Kirkpatrick, Y. Otachi, T. Saitoh, R. Uehara, and Y. Uno · 2015
Later among the works it cites.
Swapping labeled tokens on complete split graphs
G. Yasui, K. Abe, K. Yamanaka, and T. Hirayama · 2015
Later among the works it cites.
Approximation and Hardness of Token Swapping
T. Miltzow, L. Narins, Y. Okamoto, G. Rote, A. Thomas, and T. Uno · 2016
Closest in time.
Complexity of Token Swapping and its Variants
É. Bonnet, T. Miltzow, and P. Rzazewski · 2017
Closest in time.
Complexity of finding perfect bipartite matchings minimizing the number of intersecting edges
G. Guśpiel · 2017
Closest in time.