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

Finding Maximum Matching in Bipartite Graphs

on a Single-Channel Broadcast

Communication Model

**Nan-Ling Kuo and Jang-Ping Sheu ^{+}**

Tatung Institute of Technology

Taipei, Taiwan, R.O.C.

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*(*n*^{2.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*(*n*^{1.5}) time using *O*(*n*) processors where the broadcast conflict can be resolved in a constant time, while it takes *O*(*n*^{1.5}*log 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.