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