返回Google圖書搜尋

A Perfect Speedup Parallel Algorithm for the Assignment Problem on Complete Weighted Bipartite Graphs

出版	Queen's University of Kingston. Department of Computing and Information Science, 1989
URL	http://books.google.com.hk/books?id=nNGtMQEACAAJ&hl=&source=gbs_api

註釋In this paper, we present an adaptive parallel algorithm for the assignment problem of a complete weighted bipartite graph, where the edge weights can be real valued. The algorithm is designed using the exclusive-read exclusive-write parallel random-access machine (EREW PRAM) model of parallel computation. For a complete weighted bipartite graph of n verticies, the algorithm runs in O(n[superscript 3]/p + n[superscript 2]p) time using p processors. We obtain a perfect speedup, with respect to the O(n[superscript 3]) Hungarian method, for p [lesser than or equal to the square root of n]."