Previous [1] [2] [3] [4] [5]

Journal of Inforamtion Science and Engineering, Vol.6 No.1, pp.37-49 (March 1990)
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.

Keywords: maximum matching, parallel algorithm, bipartite graph

Received July 20, 1988; revised October 23, 1989.
Communicated by Wen-Tsuen Chen.