Exact upper bound for sorting R_n with LE

DOI10.1142/S1793830920500330MaRDI QIDQ4965903zbMATH OpenFDO

Authors Sai Satwik Kuppili, Bhadrachalam Chitturi

Publication date 18 March 2021

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

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

zbMATH Keywords

Cayley graphspair-exchangepermutationsset-rotatesortingupper 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

• Short proofs for cut-and-paste sorting of permutations
• A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
• Sorting by insertion of leading elements
• A new upper bound for sorting permutations with prefix transpositions
• Tighter upper bound for sorting permutations with prefix transpositions

Cites work

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

Cited in

(2)

• Sorting by insertion of leading elements
• Generation of the symmetric group \(S_{n^2}\)

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Exact upper bound for sorting \(R_n\) with LE

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