The authors’ main result improves the known processor bound by a factor of n4 (maintaining the expected parallel running time, O(log3n)) for the following important problem: find a perfect matching in a general or in a bipartite graph with n vertices. A solution to that problem is used in parallel algorithms for several combinatorial problems, in particular for the problems of finding (i) a (perfect) matching of maximum weight, (ii) a maximum cardinality matching, (iii) a matching of maximum vertex weight, (iv) a maximum s-t flow in a digraph with unit edge capacities. Consequently the known algorithms for those problems are substantially improved.
