Laszlo Lovasz recently posed the following problem: “Is there an NC algorithm for testing if a given graph has a unique perfect matching.” We present such an NC algorithm. The ideas developed may be a step towards obtaining an NC algorithm for determining if a graph has a perfect matching. We also give NC algorithms for obtaining a transitive orientation for a comparability graph, anad an interval representation for an interval graph. These enable us to obtain an NC algorithm for finding a maximum matching in incomparability graphs.
Supported by NSF Grant MCS 82-04506, and an IBM Graduate Fellowship.
Supported by NSF Grant BCR 85-03611, and an IBM Faculty Development Award.