TY - JOUR

T1 - Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree

AU - Shen, Hong

N1 - Funding Information:
*Work partially supported by an Australian Research Council Grant and done during the author's visit at Abo Akademi University. +e-mail: [email protected]

PY - 2000

Y1 - 2000

N2 - Let G be a connected, undirected and weighted graph with n vertices and m edges. A most vital edge of G with respect to minimum spanning tree is an edge whose removal from G results in the greatest weight-increase in the minimum spanning tree of the remaining graph. This paper presents a fast parallel algorithm that computes the most vital edge of G in O(log n) time using O(max{n, m log log log n/log n}) processors on a CRCW PRAM and O(log nlog log n) time using O(max{m, n2/(log n log log n)}) processors on an EREW PRAM respectively. It significantly improves the known results of O(log n) time and O(m) processors on the CRCW PRAM, and of O(log2n) time and O(n2/log2n) processors on the CREW PRAM, and O(n1+ε) time using n1-ε processors and O(m log(m/N)/N + nα(m, n)log(m/n)) time using N ≤ m log m/(nα(m, n)log(m/n)) processors on the EREW PRAM, respectively.

AB - Let G be a connected, undirected and weighted graph with n vertices and m edges. A most vital edge of G with respect to minimum spanning tree is an edge whose removal from G results in the greatest weight-increase in the minimum spanning tree of the remaining graph. This paper presents a fast parallel algorithm that computes the most vital edge of G in O(log n) time using O(max{n, m log log log n/log n}) processors on a CRCW PRAM and O(log nlog log n) time using O(max{m, n2/(log n log log n)}) processors on an EREW PRAM respectively. It significantly improves the known results of O(log n) time and O(m) processors on the CRCW PRAM, and of O(log2n) time and O(n2/log2n) processors on the CREW PRAM, and O(n1+ε) time using n1-ε processors and O(m log(m/N)/N + nα(m, n)log(m/n)) time using N ≤ m log m/(nα(m, n)log(m/n)) processors on the EREW PRAM, respectively.

UR - http://www.scopus.com/inward/record.url?scp=0033657803&partnerID=8YFLogxK

U2 - 10.1080/00207160008804971

DO - 10.1080/00207160008804971

M3 - Article

AN - SCOPUS:0033657803

SN - 0020-7160

VL - 75

SP - 129

EP - 136

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 2

ER -