An EP Algorithm for Computing a Minimum Weight Perfect Matching for a Set of Points on the Plane

Given a graph induced by an even number of points on the plane, the minimum weight matching problem calls for finding a pairing of all the points such that the sum of the distances between the paired points is the smallest possible. In this paper, we propose a parallel algorithm for this problem. The algorithm is designed for the EREW PRAM model of parallel computation with p processors. For points on the Euclidean and manhattan planes, the algorithm executes in O((n^2.5log⁴n)/p) time, where p ≤ n^0.5. The algorithm provides an optimal speedup with respect to the fastest existing sequential algorithm.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.