AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS
From MaRDI portal
Publication:2890993
DOI10.1142/S1793830911001280zbMath1408.05005MaRDI QIDQ2890993
Cedric Chauve, Marni Mishna, Dominique Rossin, Mathilde Bouvel
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
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