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 analysis; simple permutations; genome rearrangements; tree parameters

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W40: Analysis of algorithms

68P10: Searching and sorting

05A15: Exact enumeration problems, generating functions

05A05: Permutations, words, matrices

Related Items

A decorated tree approach to random permutations in substitution-closed classes, Some families of trees arising in permutation analysis, An algorithm for deciding the finiteness of the number of simple permutations in permutation 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