Tolerating linear number of faults in networks of bounded degree
E. Upfal
PODC 1992
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ó.
E. Upfal
PODC 1992
Miklos Ajtai, Avi Wigderson
FOCS 1984
N. Shavit, E. Upfal, et al.
Theory of Computing Systems
E. Upfal
STOC 1989