The Time Complexity of the Token Swapping Problem and Its Parallel Variants
From MaRDI portal
Publication:2980932
DOI10.1007/978-3-319-53925-6_35zbMath1485.68108OpenAlexW2564453173MaRDI QIDQ2980932
Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka
Publication date: 5 May 2017
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-53925-6_35
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (7)
Sequentially Swapping Colored Tokens on Graphs ⋮ Token Swapping on Trees ⋮ The Time Complexity of the Token Swapping Problem and Its Parallel Variants ⋮ The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant ⋮ Swapping colored tokens on graphs ⋮ Discrete coalescent trees ⋮ Introduction to reconfiguration
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- The complexity of finding minimum-length generator sequences
- The Time Complexity of the Token Swapping Problem and Its Parallel Variants
- Swapping Colored Tokens on Graphs
- The minimum-length generator sequence problem is NP-hard
- Paths, Trees, and Flowers
- How to write a permutation as a product of involutions (and why you might care)
This page was built for publication: The Time Complexity of the Token Swapping Problem and Its Parallel Variants
