Geodesic
The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the 11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017 , Tome 23 (2019) no. 1, pp. 29-70.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

The problems of Permutation Routing via Matching and Token Swapping are reconfiguration problems on graphs. This paper is concerned with the complexity of those problems and a colored variant. For a given graph where each vertex has a unique token on it, those problems require to find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. While all pairs of tokens on a matching can be exchanged at once in Permutation Routing via Matching, Token Swapping allows only one pair of tokens can be swapped. In the colored version, vertices and tokens are colored and the goal is to relocate tokens so that each vertex has a token of the same color. We investigate the time complexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.
DOI : 10.7155/jgaa.00483
Keywords: reconfiguration problem, routing via matching, token swapping, NP-completeness, polynomial time algorithms 
@article{JGAA_2019_23_1_a2,
     author = {Jun Kawahara and Toshiki Saitoh and Ryo Yoshinaka},
     title = {The {Time} {Complexity} of {Permutation} {Routing} via {Matching,} {Token} {Swapping} and a {Variant}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {29--70},
     publisher = {mathdoc},
     volume = {23},
     number = {1},
     year = {2019},
     doi = {10.7155/jgaa.00483},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00483/}
}
TY  - JOUR
AU  - Jun Kawahara
AU  - Toshiki Saitoh
AU  - Ryo Yoshinaka
TI  - The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
JO  - Journal of Graph Algorithms and Applications
PY  - 2019
SP  - 29
EP  - 70
VL  - 23
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00483/
DO  - 10.7155/jgaa.00483
LA  - en
ID  - JGAA_2019_23_1_a2
ER  - 
%0 Journal Article
%A Jun Kawahara
%A Toshiki Saitoh
%A Ryo Yoshinaka
%T The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
%J Journal of Graph Algorithms and Applications
%D 2019
%P 29-70
%V 23
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00483/
%R 10.7155/jgaa.00483
%G en
%F JGAA_2019_23_1_a2
Jun Kawahara; Toshiki Saitoh; Ryo Yoshinaka. The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the 11th International Conference and  Workshops on Algorithms and Computation, WALCOM 2017
					, Tome 23 (2019) no. 1, pp. 29-70. doi : 10.7155/jgaa.00483. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00483/

Cité par Sources :