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

DOI10.1007/978-3-319-53925-6_35MaRDI QIDQ2980932zbMATHOpenAlexFDO

Authors 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The time complexity of permutation routing via matching, token swapping and a variant
• Complexity of token swapping and its variants
• Complexity of token swapping and its variants
• Swapping colored tokens on graphs
• Swapping Colored Tokens on Graphs

Cites work

• scientific article; zbMATH DE number 3938577 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Approximation and hardness of token swapping
• How to write a permutation as a product of involutions (and why you might care)
• Paths, Trees, and Flowers
• Swapping Colored Tokens on Graphs
• The complexity of computing the permanent
• The complexity of finding minimum-length generator sequences
• The minimum-length generator sequence problem is NP-hard
• The time complexity of the token swapping problem and its parallel variants

Cited in

(11)

• On the Parameterized Complexity for Token Jumping on Graphs
• The time complexity of permutation routing via matching, token swapping and a variant
• Sequentially swapping colored tokens on graphs
• The time complexity of the token swapping problem and its parallel variants
• Discrete coalescent trees
• Complexity of token swapping and its variants
• Complexity of token swapping and its variants
• Swapping colored tokens on graphs
• Token Swapping on Trees
• Introduction to reconfiguration
• Polynomial time algorithms for the token swapping problem on cographs

This page was built for publication: The time complexity of the token swapping problem and its parallel variants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2980932)