Institution: Stanford University, Department of Computer Science

Title: Constructing a perfect matching is in Random NC

Author: Karp, Richard M.

Author: Upfal, Eli

Author: Wigderson, Avi

Date: March 1985

Abstract: We show that the problem of constructing a perfect matching in a graph is in the complexity class Random NC: i.e., the problem is solvable in polylog time 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: (i) Constructing a perfect matching of maximum weight in a graph whose edge weights are given in unary notation; (ii) Constructing a maximum-cardinality matching; (iii) Constructing a matching covering a set of vertices of maximum weight in a graph whose vertex weights are given in binary; (iv) Constructing a maximum s-t flow in a directed graph whose edge weights are given in unary.

http://i.stanford.edu/pub/cstr/reports/cs/tr/85/1043/CS-TR-85-1043.pdf