Improved upper bound for sorting permutations by prefix transpositions

DOI10.1016/j.tcs.2021.10.012OpenAlexW3205145651MaRDI QIDQ2664958

Pramod P. Nair, Bhadrachalam Chitturi, Rajan Sundaravaradhan

Publication date: 18 November 2021

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2021.10.012

zbMATH Keywords

permutationssortingupper boundtranspositionsprefix transpositions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Tighter upper bound for sorting permutations with prefix transpositions
• Bounding prefix transposition distance for strings and permutations
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Bounds for sorting by prefix reversal
• On the average number of reversals needed to sort signed permutations
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Sorting by Transpositions Is Difficult
• Transforming cabbage into turnip
• Edit Distances and Factorisations of Even Permutations
• A group-theoretic model for symmetric interconnection networks
• Sorting by Transpositions
• A new upper bound for sorting permutations with prefix transpositions

This page was built for publication: Improved upper bound for sorting permutations by prefix transpositions