THE DESIGN AND ANALYSIS OF ALGORITHMS AND DATA STRUCTURES FOR THE EFFICIENT SOLUTION OF GRAPH THEORETIC PROBLEMS ON MIMD COMPUTERS

The problem of developing efficient algorithms and data structures to solve graph theoretic problems on tightly-coupled MIMD computers is addressed. Several approaches to parallelizing a serial algorithm are examined. A technique is developed which allows the prediction of the expected execution time of some kinds of parallel algorithms. This technique can be used to determine which parallel algorithm is best for a particular application.; Two parallel approximate algorithms for the Euclidean traveling salesman problem are designed and analyzed. The algorithms are parallelizations of the farthest-insertion heuristic and Karp's partitioning algorithm.; Software lockout, the delay of processes due to contention for a shared data structure, can be a significant hindrance to obtaining satisfactory speedup. Using the tactics of indirection and replication, new data structures are devised which can reduce the severity of software lockout.; Finally, an upper bound to the speedup of parallel branch-and-bound algorithms which use the best-bound search strategy is determined.; ('+)This work was partially supported by U.S. Army Research Office grant number DAAG-82-K-0107 and National Science Foundation equipment grant number MCS-8203868.