Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333037 | Journal of Computer and System Sciences | 2005 | 21 Pages |
Abstract
Finally, we present the first efficient parallel algorithm for SBR. We obtain this result by developing a fast implementation of the recent algorithm of Bergeron (Proceedings of CPM, 2001, pp. 106-117) for sorting signed permutations by reversals that is parallelizable. Our implementation runs in O(n2logn) time on a regular RAM, and in O(nlogn) time on a PRAM using n processors.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Haim Kaplan, Elad Verbin,