A parallel shortest augmenting path algorithm for the assignment problem
Egon Balas, Donald L. Miller, Joseph F. Pekny, Paolo Toth · Journal of the ACM · 1991
A parallel version of the shortest augmenting path algorithm for the assignment problem 1s described.Although generating the initial dual solution and partial assignment in parallel does not require substantive changes in the sequential algorlthm, using several augmenting paths in parallel does require a new dual variable recalculation Graph Theory -graph algorithms; network problems: path and cmcmt problems: I. 1.