Common Intervals of Multiple Permutations

Steffen Heber, Richard Mayr, Jens Stoye

Research output: Contribution to journalArticlepeer-review

Abstract

Given k permutations of n elements, a k-tuple of intervals of these permutations consisting of the same set of elements is called a common interval. We present an algorithm that finds in a family of k permutations of n elements all z common intervals in optimal O(kn+z) time and O(n) additional space. Additionally, we show how to adapt this algorithm to multichromosomal and circular permutations. This extends a result by Uno and Yagiura (Algorithmica 26:290--309, 2000) who present an algorithm to find all z common intervals of k=2 (regular) permutations in optimal O(n+z) time and O(n) space. To achieve our result, we introduce the set of irreducible intervals, a generating subset of the set of all common intervals of k permutations.
Original languageEnglish
Pages (from-to)175-206
Number of pages32
JournalAlgorithmica
Volume60
Issue number2
DOIs
Publication statusPublished - Jun 2011

Keywords

  • Common intervals of permutations
  • Multichromosomal permutations
  • Circular permutations

Fingerprint Dive into the research topics of 'Common Intervals of Multiple Permutations'. Together they form a unique fingerprint.

Cite this