A Parallel Matching Algorithm for a Special Convex Bipartite Graph on an EREW PRAM Model


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 2, pp. 335-341, Feb. 1998
10.3745/KIPSTE.1998.5.2.335,   PDF Download:

Abstract

In this paper, we consider the problem of finding a maximum matching for a special convex bipartite graph. The problem arises frequently in diverse application areas such as scheduling problems. In this paper, we present an optimal parallel matching algorithm on an EREW PRAM model. We first analyze a sequential matching algorithm; then we show how to find parallelism from its inherent sequential property by deriving a formula. And we design the parallel matching algorithm using the formula. Time complexity of the algorithm is O(log n) on an EREW PRAM with n processors.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. M. Ho and J. C. Sung, "A Parallel Matching Algorithm for a Special Convex Bipartite Graph on an EREW PRAM Model," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 5, no. 2, pp. 335-341, 1998. DOI: 10.3745/KIPSTE.1998.5.2.335.

[ACM Style]
Kim Myung Ho and Jung Chang Sung. 1998. A Parallel Matching Algorithm for a Special Convex Bipartite Graph on an EREW PRAM Model. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 5, 2, (1998), 335-341. DOI: 10.3745/KIPSTE.1998.5.2.335.