首页   按字顺浏览 期刊浏览 卷期浏览 AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE*
AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE*

 

作者: CONSTANTINEN. K. OSIAKWAN,   SELIMG. AKL,  

 

期刊: Parallel Algorithms and Applications  （Taylor Available online 1994）
卷期: Volume 4, issue 3-4  

页码: 193-210

 

ISSN:1063-7192

 

年代: 1994

 

DOI:10.1080/10637199408915464

 

出版商: Taylor & Francis Group

 

关键词: Matching;assignment problem;parallel algorithm;optimal speedup;PRAM;RPRAM;F.2.1

 

数据来源: Taylor

 

摘要:

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(n3/p2+ n2logn+n2.5logn/p) time for p < equation pending We achieve a perfect speedup algorithm when p equation pending

 

点击下载:  PDF (376KB)



返 回