The time complexity of the token swapping problem and its parallel variants

Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka

研究成果: 書籍の章/レポート/Proceedings会議への寄与査読

20 被引用数 (Scopus)

抄録

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 unique token on it, the TSP requires to find a shortest way to modify a token placement into another by swapping tokens on adjacent vertices. 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. Their parallel versions allow simultaneous swaps on non-incident edges in one step. We investigate the time complexity of several restricted cases of those problems and show when those problems become tractable and remain intractable.

本文言語英語
ホスト出版物のタイトルWALCOM
ホスト出版物のサブタイトルAlgorithms and Computation - 11th International Conference and Workshops, WALCOM 2017, Proceedings
編集者Md. Saidur Rahman, Hsu-Chun Yen, Sheung-Hung Poon
出版社Springer Verlag
ページ448-459
ページ数12
ISBN(印刷版)9783319539249
DOI
出版ステータス出版済み - 2017
イベント11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017 - Hsinchu, 台湾省、中華民国
継続期間: 2017 3月 292017 3月 31

出版物シリーズ

名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
10167 LNCS
ISSN(印刷版)0302-9743
ISSN(電子版)1611-3349

会議

会議11th International Conference and Workshops on Algorithms and Computation, WALCOM 2017
国/地域台湾省、中華民国
CityHsinchu
Period17/3/2917/3/31

フィンガープリント

「The time complexity of the token swapping problem and its parallel variants」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル