The Time Complexity of the Token Swapping Problem and Its Parallel Variants.
WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings.,
, pp.448-459
(2017), [peer-reviewed]
Event Date:
March 29-31, 2017
Abstract / 概要
The token swapping problem (TSP) and its colored version are reconfiguration problems on graphs. This paper is concerned with the complexity of the TSP and two new variants; namely parallel TSP and parallel colored TSP. For a given graph where each vertex has a…