AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗

∗This research was supported by the Natural Sciences and Engineering Research Council of Canada under grant A3336.

Abstract

We consider a parallel algorithm for minimum weight perfect matching on complete bipartite graphs induced by two disjoint sets of points on the plane. The algorithm is designed for the EREW PRAM or EREW RPRAM model of parallel computation with p (a function of n) processors. For points on the Euclidean plane, the algorithm executes in O(n ³/ p ² + n2log n + n ^2.5log n/p) time for p < equation pending We achieve a perfect speedup algorithm when p equation pending

KEY WORDS:

• Matching
• assignment problem
• parallel algorithm
• optimal speedup
• PRAM
• RPRAM

C.R. CATEGORIES:

• F.2.1

Notes

∗This research was supported by the Natural Sciences and Engineering Research Council of Canada under grant A3336.