Constructing the spanners of graphs in parallel

Given a connected graph G=(V,E) with n vertices, a subgraph G´ is an approximate t-spanner of G if, for every u, ν∈V, the distance between, u and ν in G´ 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 for 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, where D is the maximum edge weight of a minimum spanning tree of G, k is a fixed constant integer, and 1⩽k⩽log_tn. Also, an NC algorithm for finding a 2t-spanner on a weighted graph G is presented. The algorithms are for a CRCW PRAM model