Fjällström, P.-O. (1996). Parallel Interval-Cover Algorithms for Coarse Grained Multicomputers. Technical Report LiTH-IDA-R-96-39, Department of Computer and Information Science, Linköping University, Sweden. (bibtex),
Abstract: This paper presents sequential and parallel algorithms for interval-cover minimization problems. That is, given a set S of (weighted) intervals on the real line, and an interval [a,b], we want to find a subset of S that is a minimum cardinality or a minimum weight cover of [a,b]. The efficiency of our parallel algorithms depends on the relationship between n and p. More specifically, our parallel algorithm for the minimum cardinality cover problem gives an optimal speedup when Ts(p,p) is O(log n), where Ts(n,p) is the time to sort n elements evenly distributed over p processors. For the minimum weight cover problem, we obtain an optimal speedup when Tr(p,p) is O(n/p), where Tr(n,p) is the time to find the maximum of n elements evenly distributed over p processors.
CS Dept TR Overview