Approximation and hardness of token swapping

DOI10.4230/LIPICS.ESA.2016.66MaRDI QIDQ4606338zbMATH OpenFDO

Authors Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, Takeaki Uno

Publication date 2 March 2018

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

zbMATH Keywords

graph theoryapproximation algorithmsNP-hardnesstoken swappingminimum generator sequence

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Complexity of token swapping and its variants
• Complexity of token swapping and its variants
• Swapping labeled tokens on graphs
• Swapping colored tokens on graphs
• Sequentially swapping colored tokens on graphs

Cited in

(18)

• 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
• Sequentially swapping colored tokens on graphs
• Improving quantum computation by optimized qubit routing
• Connecting the dots (with minimum crossings)
• Swapping colored tokens on graphs
• Complexity of token swapping and its variants
• Shortest reconfiguration of perfect matchings via alternating cycles
• Complexity of token swapping and its variants
• Reconfiguration of connected graph partitions
• Introduction to reconfiguration
• Algorithmic theory of qubit routing
• On the diameters of friends-and-strangers graphs
• Multivariate complexity analysis of Swap Bribery
• How to sort by walking and swapping on paths and trees
• scientific article; zbMATH DE number 7559364 (Why is no real title available?)
• Token Swapping on Trees

This page was built for publication: Approximation and hardness of token swapping

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