Tighter upper bound for sorting permutations with prefix transpositions
From MaRDI portal
Publication:497672
DOI10.1016/j.tcs.2015.07.059zbMath1330.05004OpenAlexW1131689765MaRDI QIDQ497672
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
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