Donald Bren School of Information and Computer Sciences

We present optimal parallel algorithms to find maximal matchings in two classes of sparse graphs, namely, graphs with bou.nded degree and those which, for some p, are forbidden to have the clique Kp as a minor. This latter class is quite large; for example, planar graphs satisfy this condition, as do graphs with any fixed bound on their genus. Our algorithms use O(log n) time on a CRCW PRAM for both classes of graphs. On an EREW PRAM, our algorithms use O(log n) time for graphs with bounded degree and O(log n log* n) time for graphs with forbidden Kp-minors.