AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS

DOI10.1142/S1793830911001280zbMath1408.05005MaRDI QIDQ2890993

Mathilde Bouvel, Cedric Chauve, Dominique Rossin, Marni Mishna

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

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

Related Items (3)

Some families of trees arising in permutation analysis ⋮ An algorithm for deciding the finiteness of the number of simple permutations in permutation classes ⋮ A decorated tree approach to random permutations in substitution-closed classes

Cites Work

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

This page was built for publication: AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS