Constructing the spanners of graphs in parallel

Weifa Liang; Richard P. Brent

doi:10.1109/ipps.1996.508059

Constructing the spanners of graphs in parallel

Weifa Liang
, Richard P. Brent

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

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

Original language	English
Pages (from-to)	206-210
Journal	IEEE Symposium on Parallel and Distributed Processing - Proceedings
DOIs	https://doi.org/10.1109/ipps.1996.508059
Publication status	Published - 1996
Externally published	Yes
Event	Proceedings of the 1996 10th International Parallel Processing Symposium - Honolulu, HI, USA Duration: 15 Apr 1996 → 19 Apr 1996

Bibliographical note

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

Access Output

10.1109/ipps.1996.508059

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{b2bf48ecdd2440ac8ccb2a71fb7c77f9,

title = "Constructing the spanners of graphs in parallel",

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 ε 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.",

author = "Weifa Liang and Brent, \{Richard P.\}",

note = "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].; Proceedings of the 1996 10th International Parallel Processing Symposium ; Conference date: 15-04-1996 Through 19-04-1996",

year = "1996",

doi = "10.1109/ipps.1996.508059",

language = "English",

pages = "206--210",

journal = "IEEE Symposium on Parallel and Distributed Processing - Proceedings",

issn = "1063-6374",

}

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 - https://www.scopus.com/pages/publications/0029710834

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 -

Constructing the spanners of graphs in parallel

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this