M. A. Bender, M. Gastaldo, and M. Morvan, "Parallel
interval order recognition and construction of interval
representations",  Theoretical Computer Science, 1995, Vol. 143,
pp. 73-91.
<P>

The authors propose parallel algorithms for solving the following
scheduling problem: we have $n$ tasks $t_1,...,t_n$, 
and we have selected $m$ pairs $(t_{f(i)},t_{s(i)})$ 
of these tasks ($1\le i\le m$) that must overlap in time. We must
 schedule these $m$ tasks (i.e., map each of them into a time
interval) in such a way that only intervals that correspond to 
$m$ given pairs of tasks overlap, and intervals corresponding to other
pairs don't overlap. The proposed algorithms run in time $O(\log(n))$
on $n+m$ processors and in constant time on $O(n^2)$ processors.