@TECHREPORT{R-96-39,
NUMBER = {R-96-39},
INSTITUTION = ida,
ADDRESS = idaaddr,
YEAR = {1996},
AUTHOR = {Fj{\"a}llstr{\"o}m, Per-Olof},
TITLE = {Parallel Interval-Cover Algorithms for Coarse Grained Multicomputers
},
ABSTRACTURL = {/publications/cgi-bin/tr-fetch.pl?r-96-39+abstr},
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.
}