Upper bounds for sorting permutations with a transposition tree

DOI10.1142/S1793830913500031MaRDI QIDQ4928334zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Cayley graphsdiametergraph algorithmsgreedy algorithmspermutationssortingstringstransposition treesupper bound

Mathematics Subject Classification ID

Distance in graphs (05C12) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Enumeration in graph theory (05C30) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• A group-theoretic model for symmetric interconnection networks
• A note on complexity of genetic mutations
• Adjacent Swaps on Strings
• An (18/11)n upper bound for sorting by prefix reversals
• Bounding prefix transposition distance for strings and permutations
• Bounds for sorting by prefix reversal
• Complete rotations in Cayley graphs
• Factoring, into edge transposition of a tree, permutations fixing a terminal vertex
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Introduction to algorithms
• Prefix Reversals on Binary and Ternary Strings
• Reversals and Transpositions Over Finite Alphabets
• Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• The complexity of finding minimum-length generator sequences

Cited in

(4)

• 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
• On the strictness of a bound for the diameter of Cayley graphs generated by transposition trees

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)