Fast algorithms to enumerate all common intervals of two permutations

DOI10.1007/S004539910014MaRDI QIDQ1969959zbMATH OpenOpenAlexFDO

Authors Takeaki Uno, Mutsunori Yagiura

Publication date 19 March 2000

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s004539910014

zbMATH Keywords

common intervals of permutationsrandom permutations

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Nonnumerical algorithms (68W05)

Recommendations

• Common intervals of multiple permutations
• scientific article; zbMATH DE number 1786460
• Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs
• \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
• Extending common intervals searching from permutations to sequences

Cited in

(25)

• Algorithmic aspects of a general modular decomposition theory
• Fully dynamic representations of interval graphs
• Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints
• \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations
• Character sets of strings
• Competitive graph searches
• Fast algorithms for identifying maximal common connected sets of interval graphs
• Average-case analysis of perfect sorting by reversals
• Algorithms for computing bidirectional best hit r-window gene clusters
• scientific article; zbMATH DE number 2127712 (Why is no real title available?)
• A fast algorithm for multiplying min-sum permutations
• New applications of interval generators to genome comparison
• scientific article; zbMATH DE number 1786460 (Why is no real title available?)
• A survey of the algorithmic aspects of modular decomposition
• Extending common intervals searching from permutations to sequences
• The potential of family-free genome comparison
• Combinatorial Pattern Matching
• Common intervals of multiple permutations
• Common intervals in permutations
• An algorithmic view of gene teams
• Fully dynamic algorithm for recognition and modular decomposition of permutation graphs
• Approximate search for known gene clusters in new genomes using PQ-trees
• Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings
• Common intervals of trees
• New algorithms for text fingerprinting

This page was built for publication: Fast algorithms to enumerate all common intervals of two permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1969959)