Average-case analysis of perfect sorting by reversals

DOI10.1142/S1793830911001280zbMATH Open1408.05005MaRDI QIDQ2890993FDOQ2890993

Authors: Mathilde Bouvel, Cedric Chauve, Marni Mishna, Dominique Rossin 

Publication date: 12 June 2012

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Recommendations

• Average-Case Analysis of Perfect Sorting by Reversals
• Algorithms – ESA 2004
• A note on average-case sorting
• On the average number of reversals needed to sort signed permutations
• Computing and Combinatorics
• scientific article; zbMATH DE number 5525701
• An approximation algorithm for sorting by reversals and transpositions
• Optimal average case sorting on arrays
• Advances on sorting by reversals

zbMATH Keywords

algorithm analysissimple permutationsgenome rearrangementstree parameters

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Searching and sorting (68P10)

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Finding pattern matchings for permutations
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• A calculus for the random generation of labelled combinatorial structures
• Transforming cabbage into turnip
• Advances on sorting by reversals
• Simple permutations and pattern restricted permutations
• Fast algorithms to enumerate all common intervals of two permutations
• Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
• A more efficient algorithm for perfect sorting by reversals
• The Asymptotic Distribution of Runs of Consecutive Elements

Cited In (8)

• A note on average-case sorting
• Efficient sample sort and the average case analysis of PEsort
• An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
• A more efficient algorithm for perfect sorting by reversals
• On the average number of reversals needed to sort signed permutations
• A decorated tree approach to random permutations in substitution-closed classes
• Some families of trees arising in permutation analysis
• Average-Case Analysis of Perfect Sorting by Reversals

This page was built for publication: Average-case analysis of perfect sorting by reversals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2890993)