Mg. Andrews et al., Parallel algorithms for maximum matching in complements of interval graphsand related problems, ALGORITHMIC, 26(2), 2000, pp. 263-289
Given a set of n intervals representing an interval graph, the problem of f
inding a maximum matching between pairs of disjoint (nonintersecting) inter
vals has been considered in the sequential model. In this paper we present
parallel algorithms for computing maximum cardinality matchings among pairs
of disjoint intervals in interval graphs in the EREW PRAM and hypercube mo
dels. For the general case of the problem, our algorithms compute a maximum
matching in O (log(3) n) time using O (nl log(2) n) processors on the EREW
PRAM and using n processors on the hypercubes. For the case of proper inte
rval graphs, our algorithm runs in O (log n) time using O (n) processors if
the input intervals are not given already sorted and using O (n/log n) pro
cessors otherwise, on the EREW PRAM. On n-processor hypercubes, our algorit
hm for the proper interval case takes O (log n log log n) time for unsorted
input and O (log n) time for sorted input. Our parallel results also lead
to optimal sequential algorithms for computing maximum matchings among disj
oint intervals. In addition, we present an improved parallel algorithm for
maximum matching between overlapping intervals in proper interval graphs.