Tighter upper bound for sorting permutations with prefix transpositions

DOI10.1016/J.TCS.2015.07.059MaRDI QIDQ497672zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

permutationsCayley graphsdiametersortingupper boundprefix transpositions

Mathematics Subject Classification ID

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

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

Cites work

• A group-theoretic model for symmetric interconnection networks
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• Bounding prefix transposition distance for strings and permutations
• Combinatorics of genome rearrangements.
• Sorting by Transpositions
• Sorting by bounded block-moves
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Upper bounds for sorting permutations with a transposition tree

Cited in

(10)

• Sorting permutations with transpositions in \(O(n^3)\) amortized time
• Improved upper bound for sorting permutations by prefix transpositions
• Exact upper bound for sorting \(R_n\) with LE
• A new upper bound for sorting permutations with prefix transpositions
• On Sorting by 3-Bounded Transpositions
• Approximation algorithms for sorting permutations by extreme block-interchanges
• Sorting of Permutations by Cost-Constrained Transpositions
• Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
• Bounding prefix transposition distance for strings and permutations
• A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation

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)