Upper bounds for sorting permutations with a transposition tree
DOI10.1142/S1793830913500031zbMATH Open1266.05064OpenAlexW2074078620MaRDI QIDQ4928334FDOQ4928334
Authors: Bhadrachalam Chitturi 
Publication date: 11 June 2013
Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s1793830913500031
Recommendations
- Sorting permutations with transpositions in \(O(n^3)\) amortized time
- Improved upper bound for sorting permutations by prefix transpositions
- A new upper bound for sorting permutations with prefix transpositions
- A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
- On the strictness of a bound for the diameter of Cayley graphs generated by transposition trees
permutationsCayley graphsdiametergraph algorithmsgreedy algorithmssortingstringsupper boundtransposition trees
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Number-theoretic algorithms; complexity (11Y16)
Cites Work
- Introduction to algorithms
- Title not available (Why is that?)
- Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
- A group-theoretic model for symmetric interconnection networks
- Bounds for sorting by prefix reversal
- Complete rotations in Cayley graphs
- An \((18/11)n\) upper bound for sorting by prefix reversals
- Prefix Reversals on Binary and Ternary Strings
- Bounding prefix transposition distance for strings and permutations
- Reversals and Transpositions Over Finite Alphabets
- Factoring, into edge transposition of a tree, permutations fixing a terminal vertex
- Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
- The complexity of finding minimum-length generator sequences
- A note on complexity of genetic mutations
- Adjacent Swaps on Strings
Cited In (4)
- On the strictness of a bound for the diameter of Cayley graphs generated by transposition trees
- Sorting permutations with transpositions in \(O(n^3)\) amortized time
- A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
- Tighter upper bound for sorting permutations with prefix transpositions
This page was built for publication: Upper bounds for sorting permutations with a transposition tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928334)
