Parallel algorithms for verification and sensitivity analysis of minimum spanning trees

Weifa Liang; Xiaojun Shen; Qing Hu

doi:10.1109/icpads.1994.590315

Parallel algorithms for verification and sensitivity analysis of minimum spanning trees

Weifa Liang
, Xiaojun Shen
, Qing Hu

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

To verify whether a spanning tree T(V,E) of graph G(V,E′) is a minimum spanning tree, two parallel algorithms are presented in this paper. The first algorithm requires O(logn) time and O(max{m/logn, n^3/2/logn}) processors, where |E′|=m and |V|=n. The second algorithm requires O(logn) time and O(m) processors or O(lognloglogn) time and O(max{m/logn, n}) processors. The first algorithm is optimal when G is dense, compared with its O(m) time sequential version. The second algorithm has better performance when G is sparse. By using above results, we also present an efficient algorithm for sensitivity analysis of minimum spanning trees which requires O(logn) time and O(max{m, n²/logn}) processors. All proposed algorithms in this paper are based on the parallel computational model called CREW PRAM.

Original language	English
Title of host publication	Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS
Publisher	IEEE
Pages	310-315
DOIs	https://doi.org/10.1109/icpads.1994.590315
Publication status	Published - 1994
Externally published	Yes
Event	Proceedings of the 1994 International Conference on Parallel and Distributed Systems - Hsinchu, China Duration: 19 Dec 1994 → 21 Dec 1994

Conference

Conference	Proceedings of the 1994 International Conference on Parallel and Distributed Systems
City	Hsinchu, China
Period	19/12/94 → 21/12/94

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/icpads.1994.590315

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@inproceedings{d4905602460a478f850b05c6e85e8f45,

title = "Parallel algorithms for verification and sensitivity analysis of minimum spanning trees",

abstract = "To verify whether a spanning tree T(V,E) of graph G(V,E′) is a minimum spanning tree, two parallel algorithms are presented in this paper. The first algorithm requires O(logn) time and O(max\{m/logn, n3/2/logn\}) processors, where |E′|=m and |V|=n. The second algorithm requires O(logn) time and O(m) processors or O(lognloglogn) time and O(max\{m/logn, n\}) processors. The first algorithm is optimal when G is dense, compared with its O(m) time sequential version. The second algorithm has better performance when G is sparse. By using above results, we also present an efficient algorithm for sensitivity analysis of minimum spanning trees which requires O(logn) time and O(max\{m, n2/logn\}) processors. All proposed algorithms in this paper are based on the parallel computational model called CREW PRAM.",

author = "Weifa Liang and Xiaojun Shen and Qing Hu",

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 1994 International Conference on Parallel and Distributed Systems ; Conference date: 19-12-1994 Through 21-12-1994",

year = "1994",

doi = "10.1109/icpads.1994.590315",

language = "English",

pages = "310--315",

booktitle = "Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS",

publisher = "IEEE",

address = "United States",

}

Liang, W, Shen, X & Hu, Q 1994, Parallel algorithms for verification and sensitivity analysis of minimum spanning trees. in Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS. IEEE, pp. 310-315, Proceedings of the 1994 International Conference on Parallel and Distributed Systems, Hsinchu, China, 19/12/94. https://doi.org/10.1109/icpads.1994.590315

Parallel algorithms for verification and sensitivity analysis of minimum spanning trees. / Liang, Weifa; Shen, Xiaojun; Hu, Qing.
Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS. IEEE, 1994. p. 310-315.

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Parallel algorithms for verification and sensitivity analysis of minimum spanning trees

AU - Liang, Weifa

AU - Shen, Xiaojun

AU - Hu, Qing

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 - 1994

Y1 - 1994

N2 - To verify whether a spanning tree T(V,E) of graph G(V,E′) is a minimum spanning tree, two parallel algorithms are presented in this paper. The first algorithm requires O(logn) time and O(max{m/logn, n3/2/logn}) processors, where |E′|=m and |V|=n. The second algorithm requires O(logn) time and O(m) processors or O(lognloglogn) time and O(max{m/logn, n}) processors. The first algorithm is optimal when G is dense, compared with its O(m) time sequential version. The second algorithm has better performance when G is sparse. By using above results, we also present an efficient algorithm for sensitivity analysis of minimum spanning trees which requires O(logn) time and O(max{m, n2/logn}) processors. All proposed algorithms in this paper are based on the parallel computational model called CREW PRAM.

AB - To verify whether a spanning tree T(V,E) of graph G(V,E′) is a minimum spanning tree, two parallel algorithms are presented in this paper. The first algorithm requires O(logn) time and O(max{m/logn, n3/2/logn}) processors, where |E′|=m and |V|=n. The second algorithm requires O(logn) time and O(m) processors or O(lognloglogn) time and O(max{m/logn, n}) processors. The first algorithm is optimal when G is dense, compared with its O(m) time sequential version. The second algorithm has better performance when G is sparse. By using above results, we also present an efficient algorithm for sensitivity analysis of minimum spanning trees which requires O(logn) time and O(max{m, n2/logn}) processors. All proposed algorithms in this paper are based on the parallel computational model called CREW PRAM.

UR - https://www.scopus.com/pages/publications/0028748326

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0028748326&origin=recordpage

U2 - 10.1109/icpads.1994.590315

DO - 10.1109/icpads.1994.590315

M3 - RGC 32 - Refereed conference paper (with host publication)

SP - 310

EP - 315

BT - Proceedings of the Internatoinal Conference on Parallel and Distributed Systems - ICPADS

PB - IEEE

T2 - Proceedings of the 1994 International Conference on Parallel and Distributed Systems

Y2 - 19 December 1994 through 21 December 1994

ER -

Parallel algorithms for verification and sensitivity analysis of minimum spanning trees

Abstract

Conference

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this