Parallel graph algorithms

Reviewer: Andranik Mirzaian

After an introduction and terminology section, this survey article contains a brief discussion of various parallel computational models, such as SIMD, MIMD and their variants, systolic arrays, and associative processors. There is a section on unweighted graph algorithms where such problems as graph searching, connected-components, transitive closure, biconnected-components and strongly-connected-components, lowest-common ancestors, k-connectivity, triconnectivity and testing planarity, maximum clique, and maximum cardinality matching in convex-bipartite graphs are covered. Some of these problems are given more attention than others. For instance, the fundamental problem of graph searching is well covered. The next section is on weighted-graph algorithms. In this section, the minimum spanning tree, the shortest paths, and the traveling salesman problems are covered in some detail. There is a brief mention of other problems such as max-flow. The last section gives a summary of this survey. This article contains 153 references. A few areas, as the authors acknowledge, are not covered (for instance, systolic algorithms). There is, however, a brief mention of some probabilistic algorithms. Overall, this is a good survey and is worth reading. It highlights some of the important algorithmic and data-structuring techniques developed for parallel graph computation. However, it has a number of shortcomings. Certain important work is not referenced at all, such as [1].