Average-case analysis of perfect sorting by reversals

DOI10.1142/S1793830911001280MaRDI QIDQ2890993zbMATH OpenFDO

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)

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)

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

Cites work

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

Cited in

(8)

• Efficient sample sort and the average case analysis of PEsort
• A note on average-case sorting
• 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)