Complexity of token swapping and its variants

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

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

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 (11)

• The time complexity of the token swapping problem and its parallel variants
• On a compact encoding of the swap automaton
• Swapping colored tokens on graphs
• Complexity of token swapping and its variants
• Introduction to reconfiguration
• Approximation and hardness of token swapping
• Multivariate complexity analysis of Swap Bribery
• Token Swapping on Trees
• Sequentially swapping tokens: further on graph classes
• The time complexity of permutation routing via matching, token swapping and a variant
• Polynomial time algorithms for the token swapping problem on cographs

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)