Parallel Processing for Some Large-Scale Network Optimization Problems

摘要

Techniques of designing parallel programs for solving large-scale network optimization problems are developed in the study. These techniques are illustrated with three different problems on networks. Part I, contains two distinct algorithms for solving the one-to-all shortest path problem on a tightly-coupled, multiple-instruction-stream, multiple-data-stream (MIMD) type of parallel computer. Description of the parallel algorithms developed and the novel data structures employed are included. A user's manual for the parallel programs is also given. Part II contains a parallel algorithm and its performance for solving the minimum-cost network-flow problem. A user's manual for the parallel algorithm is included. Finally, Part III consists of an extremely fast parallel algorithm for finding an approximate solution of the traveling salesman problem on an Euclidean plane. From the study it is evident that parallel computers can be used to gain speeds in processing large networks. The fifth generation computers will require an extensive body of application software.