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(tk+1)
and f(t) = O(Dtk+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 < logtn.
Also, an NC algorithm for finding a
2t-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