Fast algorithms to enumerate all common intervals of two permutations

DOI10.1007/s004539910014zbMath0949.68168OpenAlexW2044007697MaRDI 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 permutationscommon intervals of permutations

Mathematics Subject Classification ID

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

Related Items (19)

AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS ⋮ Common intervals of trees ⋮ An algorithmic view of gene teams ⋮ New applications of interval generators to genome comparison ⋮ Fully dynamic representations of interval graphs ⋮ A survey of the algorithmic aspects of modular decomposition ⋮ Extending common intervals searching from permutations to sequences ⋮ Character sets of strings ⋮ New algorithms for text fingerprinting ⋮ Algorithms for Computing Bidirectional Best Hit r-Window Gene Clusters ⋮ \textit{MinMax}-profiles: a unifying view of common intervals, nested common intervals and conserved intervals of \(K\) permutations ⋮ Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings ⋮ Common intervals of multiple permutations ⋮ Competitive graph searches ⋮ Fast algorithms for identifying maximal common connected sets of interval graphs ⋮ Common intervals and permutation reconstruction from \textit{MinMax}-betweenness constraints ⋮ Fully dynamic algorithm for recognition and modular decomposition of permutation graphs ⋮ Algorithmic aspects of a general modular decomposition theory ⋮ The Potential of Family-Free Genome Comparison

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