Complexity of token swapping and its variants

DOI10.4230/LIPICS.STACS.2017.16zbMATH Open1390.68334arXiv1607.07676MaRDI QIDQ4636614FDOQ4636614

Édouard Bonnet, Paweł Rzążewski, Tillmann Miltzow

Publication date: 19 April 2018

Full work available at URL: https://arxiv.org/abs/1607.07676

Recommendations

• Complexity of token swapping and its variants
• Approximation and hardness of token swapping
• Swapping colored tokens on graphs
• Swapping Colored Tokens on Graphs
• The time complexity of the token swapping problem and its parallel variants

zbMATH Keywords

NP-hardnessparameterized complexityW[1-hardness]token swapping

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (5)

• On a compact encoding of the swap automaton
• Swapping colored tokens on graphs
• Complexity of token swapping and its variants
• Introduction to reconfiguration
• Multivariate complexity analysis of Swap Bribery

This page was built for publication: Complexity of token swapping and its variants

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