Constructing the Spanners of Graphs in Parallel

Given a connected graph G = (V; E) with n vertices and m edges, the distance between two vertices in G is the weight of the shortest path between them. A subgraph G 0 is a t-spanner (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 t (f(t)) times longer than the distance in G, where f(t) is a polynomial function of variable t and t f(t) ! n. In this paper parallel algorithms for finding approximate t-spanners on both unweighted graphs and weighted graphs are given. If G is an unweighted graph, our algorithm requires O( n t k log n) time and M(n) processors, and the spanner generated has size of O(( n t k ) 1+1=t +n) and factor of O(t k+1 ); otherwise our algorithm requires O(( n t k ) 2 +( n t k ) 1+2=(t\Gamma2) log n) time and O(n 2 ) processors, and the spanner generated has size of O(( n t k ) 1+2=(t\Gamma1) +n), weight of (( n t k ) 2+ffl t\Gamma1 + 1)wt(MST ), and factor of O(Dt k+1 ), where M(n)..