TY - JOUR
T1 - Constructing the spanners of graphs in parallel
AU - Liang, Weifa
AU - Brent, Richard P.
N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].
PY - 1996
Y1 - 1996
N2 - 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 ε 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(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.
AB - 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 ε 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(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.
UR - http://www.scopus.com/inward/record.url?scp=0029710834&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0029710834&origin=recordpage
U2 - 10.1109/ipps.1996.508059
DO - 10.1109/ipps.1996.508059
M3 - RGC 21 - Publication in refereed journal
SN - 1063-6374
SP - 206
EP - 210
JO - IEEE Symposium on Parallel and Distributed Processing - Proceedings
JF - IEEE Symposium on Parallel and Distributed Processing - Proceedings
T2 - Proceedings of the 1996 10th International Parallel Processing Symposium
Y2 - 15 April 1996 through 19 April 1996
ER -