**Dept. of Computer and Information science, Linköping University**

## IDA Technical Reports: abstract

*Generated: Sat, 04 Jul 2015 17:22:12 *

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.

**Goto (at Linköping University):**
```
CS Dept
TR Overview
```

*<webmaster@ida.liu.se>*