A new upper bound for sorting permutations with prefix transpositions

DOI10.1142/S1793830920500779MaRDI QIDQ5859487zbMATH OpenFDO

Authors Pramod P. Nair, Rajan Sundaravaradhan, Bhadrachalam Chitturi

Publication date 16 April 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S1793830920500779

zbMATH Keywords

Cayley graphsdiameterpermutationsprefix transpositionsortingupper bound

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05)

Recommendations

• Tighter upper bound for sorting permutations with prefix transpositions
• Improved upper bound for sorting permutations by prefix transpositions
• Bounding prefix transposition distance for strings and permutations
• Lower bounding edit distances between permutations
• Edit Distances and Factorisations of Even Permutations

Cites work

• A group-theoretic model for symmetric interconnection networks
• Bounding prefix transposition distance for strings and permutations
• Sorting by bounded block-moves
• Sorting by Transpositions
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Tighter upper bound for sorting permutations with prefix transpositions

Cited in

(10)

• Approximation algorithms for sorting permutations by extreme block-interchanges
• A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
• Improved upper bound for sorting permutations by prefix transpositions
• Edit Distances and Factorisations of Even Permutations
• Upper bounds for sorting permutations with a transposition tree
• Exact upper bound for sorting \(R_n\) with LE
• Tighter upper bound for sorting permutations with prefix transpositions
• Generation of the symmetric group \(S_{n^2}\)
• Sorting of Permutations by Cost-Constrained Transpositions
• Bounding prefix transposition distance for strings and permutations

This page was built for publication: A new upper bound for sorting permutations with prefix transpositions

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