Parallel graph algorithms

Algorithms and data structures developed to solve graph problems on parallel computers are surveyed. The problems discussed relate to searching graphs and finding connected components, maximal chques, maximum cardinahty matchings, mimmum spanning trees, shortest paths, and travehng salesman tours. The algorithms are based on a number of models of parallel computation, including systohc arrays, assoclatwe processors, array processors, and mulhple CPU computers. The most popular model is a direct extension of the standard RAM model of sequential computation. It may not, however, be the best basis for the study of parallel algorithms. More emphasis has been focused recently on communications issues in the analysis of the complexity of parallel algorithms; thus parallel models are coming to be more complementary to implementable architectures. Most algorithms use relatwely simple data structures, such as the adjacency matrix and adjacency hsts, although a few algorithms using linked hsts, heaps, and trees are also discussed.