AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS
From MaRDI portal
Publication:2890993
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)
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