## 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(*t*^{k+1})
and *f(t)* = O(D*t*^{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 0 < *k* __<__ log_{t}*n*.
Also, an NC algorithm for finding a
2*t*-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