Tighter upper bound for sorting permutations with prefix transpositions
From MaRDI portal
Publication:497672
DOI10.1016/J.TCS.2015.07.059zbMATH Open1330.05004OpenAlexW1131689765MaRDI QIDQ497672FDOQ497672
Authors: 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
Recommendations
- A new 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
Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30)
Cites Work
- Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
- A group-theoretic model for symmetric interconnection networks
- Combinatorics of genome rearrangements.
- Sorting by Transpositions
- Sorting by transpositions is difficult
- Sorting by bounded block-moves
- Bounding prefix transposition distance for strings and permutations
- A simpler and faster 1.5-approximation algorithm for sorting by transpositions
- UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE
Cited In (8)
- Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
- Sorting permutations with transpositions in \(O(n^3)\) amortized time
- Sorting of Permutations by Cost-Constrained Transpositions
- Improved upper bound for sorting permutations by prefix transpositions
- Approximation algorithms for sorting permutations by extreme block-interchanges
- Bounding prefix transposition distance for strings and permutations
- On Sorting by 3-Bounded Transpositions
- A new upper bound for sorting permutations with prefix transpositions
This page was built for publication: Tighter 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 Q497672)
