Sorting a permutation by best short swaps

DOI10.1007/s00453-021-00814-xOpenAlexW3133549692MaRDI QIDQ2037101

Haitao Jiang, Haodi Feng, Xiaowen Liu, Daming Zhu, Jiong Guo, Shu Zhang

Publication date: 30 June 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-021-00814-x

zbMATH Keywords

complexityalgorithmpermutationshort swap

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• A \((1+\varepsilon)\)-approximation algorithm for sorting by short block-moves
• A 14/11-approximation algorithm for sorting by short block-moves
• The complexity of finding minimum-length generator sequences
• Sorting by short block-moves
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• A simple algorithm for the constrained sequence problems
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Transforming cabbage into turnip
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Genome Rearrangements and Sorting by Reversals
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals

This page was built for publication: Sorting a permutation by best short swaps