Complexity of token swapping and its variants

DOI10.4230/LIPICS.STACS.2017.16MaRDI QIDQ4636614zbMATH OpenFDO

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

Publication date 19 April 2018

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

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)

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

Cited in

(11)

• The time complexity of permutation routing via matching, token swapping and a variant
• Multivariate complexity analysis of Swap Bribery
• Approximation and hardness of token swapping
• The time complexity of the token swapping problem and its parallel variants
• On a compact encoding of the swap automaton
• Complexity of token swapping and its variants
• Swapping colored tokens on graphs
• Token Swapping on Trees
• Sequentially swapping tokens: further on graph classes
• Introduction to reconfiguration
• 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)