Processor efficient parallel matching
In this paper we consider the problem of finding perfect matchings in parallel. We present a RNC algorithm with almost optimal work with respect to sequential algorithms, i.e., it uses O(n(omega)) processors, where omega is the matrix multiplication exponent. Our algorithm is based on an RNC algorithm for computing determinant of a degree one polynomial matrix which is of independent interest.
rnc algorithm parallel algorithms maximum matching fast matrix multiplication