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 (158293 bytes)] [PDF (317740 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-DOT-Reports-AT-cs-DOT-anu.edu.au>

Last modified: Tue May 31 12:55:59 EST 2011