Constructing the Spanners of Graphs in Parallel

Given a connected graph G = (V; E) with n vertices, a subgraph G 0 is an approximate t-spanner of G if, for every u, v 2 V , the distance between u and v in G 0 is at most f(t) times longer than the distance in G, where f(t) is a polynomial function of t and t f(t) ! n. In this paper parallel algorithms of finding approximate t-spanners on both unweighted graphs and weighted graphs with f(t) = O(t k+1 ) and f(t) = O(Dt k+1 ) respectively are given first, where D is the maximum edge weight of a minimum spanning tree of G, k is a fixed constant integer, and 1 k log t n. Then an NC algorithm for finding a 2t-spanner on a weighted graph G is presented. The algorithms run in a CRCW PRAM model