UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE

DOI10.1142/S1793830913500031zbMath1266.05064OpenAlexW2074078620MaRDI QIDQ4928334

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

permutationssortingupper bounddiameterCayley graphsstringsgraph algorithmsgreedy algorithmstransposition trees

Mathematics Subject Classification ID

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

Related Items (2)

Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Tighter upper bound for sorting permutations with prefix transpositions

Cites Work

• Unnamed Item
• Unnamed Item
• Pancake flipping is hard
• Bounding prefix transposition distance for strings and permutations
• An \((18/11)n\) upper bound for sorting by prefix reversals
• The complexity of finding minimum-length generator sequences
• Bounds for sorting by prefix reversal
• Factoring, into edge transposition of a tree, permutations fixing a terminal vertex
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A NOTE ON COMPLEXITY OF GENETIC MUTATIONS
• Adjacent Swaps on Strings
• Prefix Reversals on Binary and Ternary Strings
• A group-theoretic model for symmetric interconnection networks
• Self-Stabilizing Algorithms for Finding Centers and Medians of Trees
• Reversals and Transpositions Over Finite Alphabets
• Complete rotations in Cayley graphs

This page was built for publication: UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE