Sorting permutations with transpositions in \(O(n^3)\) amortized time

DOI10.1016/j.tcs.2018.09.015zbMath1418.68072OpenAlexW2893559467WikidataQ129204627 ScholiaQ129204627MaRDI QIDQ1731847

Priyanshu Das, Bhadrachalam Chitturi

Publication date: 14 March 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.09.015

zbMATH Keywords

permutationscomplexitysortingdynamic programmingamortized analysistranspositions and block-moves

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10) Permutations, words, matrices (05A05) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Symmetric groups (20B30)

Related Items (1)

Exact upper bound for sorting Rn with LE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps
• Tighter upper bound for sorting permutations with prefix transpositions
• Bounding prefix transposition distance for strings and permutations
• The complexity of finding minimum-length generator sequences
• Permutations and successions
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• A simpler and faster 1.5-approximation algorithm for sorting by transpositions
• An Audit Tool for Genome Rearrangement Algorithms
• Sorting by Transpositions Is Difficult
• A New and Faster Method of Sorting by Transpositions
• A group-theoretic model for symmetric interconnection networks
• Sorting by Transpositions
• UPPER BOUNDS FOR SORTING PERMUTATIONS WITH A TRANSPOSITION TREE
• Generation of Permutations by Adjacent Transposition
• Sorting a bridge hand

This page was built for publication: Sorting permutations with transpositions in \(O(n^3)\) amortized time