Almost-optimum speed-ups of algorithms for dipartite matching and relatod problems

We present algorithms for matching and related problems that, run on an EREW PRAM with p processors. Given is a bipartite graph G with n vertices, m edges, and integral edge costs at most N in magnitude. We give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in O(√nm log(nN)(log⁽²⁾)) time and 0(m) space, for p ≤ m/(√nog²n). For p = 1 this improves the best known sequential algorithm, and is within a factor of log(nN) of the best known bound for the problem without costs (maximum cardinality matching). For p < 1 the time is within a factor of logp of optimum speed-up. Extensions include an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). Our ideas also extend to general graph matching problems.