Abstract
The problem of finding maximum matching in bipartite graphs is studied in this paper. It is known that Hopcroft and Karp's maximum matching algorithm with O(n2.5) time complexity is the best sequential one proposed so far. By implementing Hopcroft and Karp's algorithm on a single-channel broadcast communication model, we get a new parallel maximum matching algorithm. The new parallel algorithm runs in O(n1.5) time using O(n) processors where the broadcast conflict can be resolved in a constant time, while it takes O(n1.5log n) time using O(n / log n) processors if O(log n) time is needed to resolve a broadcast conflict. Thus, an optimal speedup under both cases is obtained.