Report Number: CS-TR-85-1043
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