ANU Computer Science Technical Reports

TR-CS-96-01

Weifa Liang and Richard P. Brent.
Constructing the spanners of graphs in parallel.
January 1996.
A short version will appear in Proc. of 10th Intern. Conf. on Parallel Processing Sympo., 1996.

[POSTSCRIPT (158290 bytes)]

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 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_t n. Also, an NC algorithm for finding a 2t-spanner on a weighted graph G is presented. The algorithms are for a CRCW PRAM model.

Technical Reports <Technical.Reports@cs.anu.edu.au>

Last modified: Wed May 14 08:19:37 EST 1997