Finding Maximum Matching in Bipartite Graphs on a Single-Channel Broadcast Communication Model
Nan-Ling Kuo and Jang-Ping Sheu+ Institute of Information Engineering Tatung Institute of Technology Taipei, Taiwan, R.O.C. +Department of Electrical Engineering National Central University Chungli, Taiwan 32054, R.O.C.
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.