Sorting a permutation by best short swaps

DOI10.1007/S00453-021-00814-XMaRDI QIDQ2037101zbMATH OpenOpenAlexFDO

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

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

permutationalgorithmcomplexityshort swap

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 7286740
• Sorting by short block-moves
• Short proofs for cut-and-paste sorting of permutations
• Sorting permutations by block-interchanges
• SORTING SIGNED PERMUTATIONS BY FIXED-LENGTH REVERSALS

Cites work

• scientific article; zbMATH DE number 1947393 (Why is no real title available?)
• scientific article; zbMATH DE number 7286740 (Why is no real title available?)
• A 14/11-approximation algorithm for sorting by short block-moves
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• A (1+)-approximation algorithm for sorting by short block-moves
• A simple algorithm for the constrained sequence problems
• An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Genome Rearrangements and Sorting by Reversals
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by short block-moves
• The complexity of finding minimum-length generator sequences
• Transforming cabbage into turnip

Cited in

(1)

• scientific article; zbMATH DE number 7286740 (Why is no real title available?)

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

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