AnEPAlgorithm for Computing a Minimum Weight Perfect Matching for a Set of Points on the Plane
Constantine K. N. Osiakwan, Selim G. Akl
ORSA Journal on Computing · 1994 · Volume 6 · Issue 4
Abstract
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 distan ces 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.5 log 4 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.
Keywords
analysis of algorithms, complexity
Enable JavaScript for citation tools and additional paper interactions.