Common Intervals of Multiple Permutations |
| |
| Authors: | Steffen Heber Richard Mayr Jens Stoye |
| |
| Affiliation: | 1.Department of Computer Science,North Carolina State University,Raleigh,USA;2.School of Informatics,University of Edinburgh,Edinburgh,UK;3.Technische Fakult?t,Universit?t Bielefeld,Bielefeld,Germany |
| |
| 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. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
