Constructing a perfect matching is in random NC
Richard M. Karp, Eli Upfal, Avi Wigderson · 1985
In this paper we show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC: i.e., lhe problem is solvable in polylog lime by a randomized parallel algorithm using a polynomial-bounded number of processors.We also show that several related problems lie in Random NC.These include: (9 Construcling a pcrfccl malchin$; of maximum wcighl in a gmph whose edge weights are given in unary notalion; t Kcxatuh suppoiicd by NW Grant #DCK-&111954.$ Rcscmh suppwl~xl by a Wcimnnti Posl-Docloral Qllowsbip, :1nt1 by IhI KI'A GCWI NOo39-U-C-1036.vt Kcuc:erh suppolor~rd in, part hy l)hKPh Gmnt NOOO39-82-C 0235.