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.
Keywords: maximum matching, parallel algorithm, bipartite graph
Received July 20, 1988; revised October 23, 1989.
Communicated by Wen-Tsuen Chen.