Almost-Optimum Parallel Speed-ups of Algorithms for Bipartite Matching and Related Problems

Abstract:

This paper focuses on algorithms for matching problems that run on an EREW PRAM with p processors. ... Extensions of the algorithm are given, including 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).