SOLVING SOME GRAPH PROBLEMS WITH OPTIMAL OR NEAR-OPTIMAL SPEEDUP ON MESH-OF-TREES NETWORKS.

Abstract

A systematic approach for solving graph problems under the network models is presented and illustrated on the mesh-of-trees networks. It is known that under the CREW PRAM model, when a undirected graph of n node is given by an n by n adjacency matrix, the problems of finding minimum spanning forest, connected components, and biconnected components can all be solved with optimal speedup when the number of processors p less than equivalent to n**2/log**2n. It is shown that for these problems, the same optimal speedup can be achieved even under the much more restrictive mesh-of-trees network. It is also shown that for the problem of finding directed spanning forest of arbitrary digraphs and the problem of testing strong connectivity of 1-reachable digraphs, near-optimal speedup can be achieved.