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).
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