Multiprocessor algorithms for generalized network flows
R. H. Clark, Robert R. Meyer · Minds at UW (University of Wisconsin) · 1987
This paper presents parallel algorithms for the solution of generalized network optimization problems on a shared-memory multiprocessor. These algorithms exploit the quasi-tree forest basis structure of generalized networks by attempting to perform multiple simples pivot operations in parallel on disconnected subtrees. The authors consider algorithms for both single-period generalized networks and multi-period generalized networks. In the latter case, the multi-period structure is utilized in the initial stage of the algorithms in order to initially partition the problem among processors. Computational experience on the Sequent Balance 21000 multiprocessor is present that demonstrates linear and sometimes superlinear speedup for a large class of test problems.