Exact upper bound for sorting Rn with LE

DOI10.1142/S1793830920500330zbMath1505.68007MaRDI QIDQ4965903

Bhadrachalam Chitturi, Sai Satwik Kuppili

Publication date: 18 March 2021

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

zbMATH Keywords

permutationssortingupper boundCayley graphspair-exchangeset-rotate

Mathematics Subject Classification ID

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

Related Items (1)

Generation of the symmetric group Sn2

Uses Software

• OEIS

Cites Work

• An \((18/11)n\) upper bound for sorting by prefix reversals
• The complexity of finding minimum-length generator sequences
• Greedy cycles in the star graphs
• Sorting permutations with transpositions in \(O(n^3)\) amortized time
• Large Cayley graphs of small diameter
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A NOTE ON COMPLEXITY OF GENETIC MUTATIONS
• A group-theoretic model for symmetric interconnection networks
• A FEW FAMILIES OF CAYLEY GRAPHS AND THEIR EFFICIENCY AS COMMUNICATION NETWORKS
• Sorting with fixed-length reversals

This page was built for publication: Exact upper bound for sorting Rn with LE