Title
Parallel Hungarian Algorithm
Abstract
Using an exclusive-read and exclusive-write (EREW), parallel random access machine (PRAM) with p processors, an efficient parallel algorithm is presented to solve an n × n assignment problem. The algorithm is a parallelization of the classic Hungarian method, runs in O(n3/p + n2 log p) time, and achieves optimal speedup using 1 ≤ p ≤ n/log n processors. The product processor-(time)2 is identified as an appropriate performance measure to derive the optimality condition.
Publication Date
7-1-1990
Publication Title
Computer Systems Science and Engineering
Volume
5
Issue
3
Number of Pages
131-136
Document Type
Article
Personal Identifier
scopus
Copyright Status
Unknown
Socpus ID
0025465240 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/0025465240
STARS Citation
Das, Sajal K. and Deo, Narsingh, "Parallel Hungarian Algorithm" (1990). Scopus Export 1990s. 1508.
https://stars.library.ucf.edu/scopus1990/1508