Fast algorithms to enumerate all common intervals of two permutations

DOI10.1007/s004539910014zbMath0949.68168MaRDI QIDQ1969959

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

random permutations; common intervals of permutations

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

68T05: Learning and adaptive systems in artificial intelligence

Related Items

Fully dynamic algorithm for recognition and modular decomposition of permutation graphs, New applications of interval generators to genome comparison, A survey of the algorithmic aspects of modular decomposition, Extending common intervals searching from permutations to sequences, Common intervals of multiple permutations, An algorithmic view of gene teams, Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings, Common intervals of trees, New algorithms for text fingerprinting, Algorithmic aspects of a general modular decomposition theory, \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