scientific article; zbMATH DE number 6846437

DOI10.4230/LIPIcs.ESA.2016.66zbMath1397.68146arXiv1602.05150MaRDI QIDQ4606338

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

graph theoryapproximation algorithmsNP-hardnesstoken swappingminimum generator sequence

Mathematics Subject Classification ID

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

Related Items (14)

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles ⋮ Sequentially Swapping Colored Tokens on Graphs ⋮ How to sort by walking and swapping on paths and trees ⋮ Token Swapping on Trees ⋮ Reconfiguration of connected graph partitions ⋮ Improving quantum computation by optimized qubit routing ⋮ Algorithmic theory of qubit routing ⋮ The Time Complexity of the Token Swapping Problem and Its Parallel Variants ⋮ The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant ⋮ Swapping colored tokens on graphs ⋮ Unnamed Item ⋮ Complexity of token swapping and its variants ⋮ Connecting the dots (with minimum crossings) ⋮ Introduction to reconfiguration

This page was built for publication: