Constructing the spanners of graphs in parallel

162. W. Liang and R. P. Brent, Constructing the spanners of graphs in parallel, Proceedings of the Tenth International Parallel Processing Symposium (IPPS '96), IEEE CS Press, 1996, 206-210.

A longer version appeared as Technical Report TR-CS-96-01, CSL, ANU, Jan. 1996, 16 pp.

Paper: pdf (150K), ps (51K).

Technical Report: ps (156K).

Abstract

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 in V, the distance between u and v 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(tk+1) and f(t) = O(Dtk+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 0 < k < logtn. Also, an NC algorithm for finding a 2t-spanner on a weighted graph G is presented. The algorithms are for the CRCW PRAM model.

Go to next publication

Return to Richard Brent's index page