Approximation and hardness of token swapping
DOI10.4230/LIPICS.ESA.2016.66zbMATH Open1397.68146arXiv1602.05150MaRDI QIDQ4606338FDOQ4606338
Takeaki Uno, Lothar Narins, Tillmann Miltzow, Antonis Thomas, Yoshio Okamoto, Günter Rote
Publication date: 2 March 2018
Full work available at URL: https://arxiv.org/abs/1602.05150
Recommendations
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)
Cited In (16)
- 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
- The Time Complexity of the Token Swapping Problem and Its Parallel Variants
- Reconfiguration of connected graph partitions
- Sequentially Swapping Colored Tokens on Graphs
- Algorithmic theory of qubit routing
- Introduction to reconfiguration
- On the diameters of friends-and-strangers graphs
- The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant
- Multivariate complexity analysis of Swap Bribery
- How to sort by walking and swapping on paths and trees
- Title not available (Why is that?)
- Token Swapping on Trees
- Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
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)
