Miklos Ajtai, Avi Wigderson
FOCS 1984
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. © 1986 Akadémiai Kiadó.
Miklos Ajtai, Avi Wigderson
FOCS 1984
R. Kumar, Prabhakar Raghavan, et al.
FOCS 2000
Cynthia Dwork, David Peleg, et al.
SIAM Journal on Computing
Friedhelm Meyer auf der Heide, Avi Wigderson
FOCS 1984