# 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