Tighter upper bound for sorting permutations with prefix transpositions

DOI10.1016/j.tcs.2015.07.059zbMath1330.05004OpenAlexW1131689765MaRDI QIDQ497672

Bhadrachalam Chitturi

Publication date: 25 September 2015

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

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

zbMATH Keywords

permutationssortingupper bounddiameterCayley graphsprefix transpositions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30)

Related Items (4)

Improved upper bound for sorting permutations by prefix transpositions ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Approximation algorithms for sorting permutations by extreme block-interchanges ⋮ A new upper bound for sorting permutations with prefix transpositions

Cites Work

• Unnamed Item
• Bounding prefix transposition distance for strings and permutations
• Sorting by bounded block-moves
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• Sorting by Transpositions Is Difficult
• A group-theoretic model for symmetric interconnection networks
• Sorting by Transpositions
• UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE

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