The Time Complexity of Permutation Routing via Matching, Token Swapping and a Variant

DOI10.7155/jgaa.00483zbMath1405.05174arXiv1612.02948OpenAlexW2962964818MaRDI QIDQ4622770

Jun Kawahara, Toshiki Saitoh, Ryo Yoshinaka

Publication date: 14 February 2019

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

time complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles, Algorithmic theory of qubit routing

Cites Work

• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Complexity of token swapping and its variants
• The complexity of finding minimum-length generator sequences
• Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and \(k\)-ary trees
• New results on routing via matchings on graphs
• Swapping colored tokens on graphs
• Swapping labeled tokens on graphs
• The Time Complexity of the Token Swapping Problem and Its Parallel Variants
• Routing Numbers of Cycles, Complete Bipartite Graphs, and Hypercubes
• The minimum-length generator sequence problem is NP-hard
• Optimal Bounds for Matching Routing on Trees
• Routing Permutations on Graphs via Matchings
• Reducibility among Combinatorial Problems
• Paths, Trees, and Flowers
• How to write a permutation as a product of involutions (and why you might care)
• The complexity of theorem-proving procedures