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