TY - JOUR

T1 - NC algorithms for the single most vital edge problem with respect to shortest paths

AU - Venema, Sven

AU - Shen, Hong

AU - Suraweera, Francis

PY - 1996/12/9

Y1 - 1996/12/9

N2 - For a weighted, undirected graph G = (V, E), the single most vital edge in a network with respect to shortest paths is the edge that, when removed, results in the greatest increase in the shortest distance between two nodes s and t. We give a sequential algorithm for the Single Most Vital Edge problem on weighted and undirected graphs. Our algorithm has a time complexity O(mα(m,n)), where n =| V |, m =| E |, and α(m,n) is a functional inverse of Ackermann's function. This algorithm eliminates the inherent sequentiality of the algorithm due to Malik et al. We also obtain a set of parallel algorithms running in O(log n) time using m processors and O(m) space on the CRCW PRAM, in O(log n) time using mn/log n CREW processors and O(m + n log m) space, and in O(log n) time using mn/ log n EREW processors and O(mn) space, respectively. These are the first NC algorithms for solving this problem on the PRAM.

AB - For a weighted, undirected graph G = (V, E), the single most vital edge in a network with respect to shortest paths is the edge that, when removed, results in the greatest increase in the shortest distance between two nodes s and t. We give a sequential algorithm for the Single Most Vital Edge problem on weighted and undirected graphs. Our algorithm has a time complexity O(mα(m,n)), where n =| V |, m =| E |, and α(m,n) is a functional inverse of Ackermann's function. This algorithm eliminates the inherent sequentiality of the algorithm due to Malik et al. We also obtain a set of parallel algorithms running in O(log n) time using m processors and O(m) space on the CRCW PRAM, in O(log n) time using mn/log n CREW processors and O(m + n log m) space, and in O(log n) time using mn/ log n EREW processors and O(mn) space, respectively. These are the first NC algorithms for solving this problem on the PRAM.

KW - Algorithms

KW - NC algorithms

KW - Parallel processing

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

U2 - 10.1016/S0020-0190(96)00172-X

DO - 10.1016/S0020-0190(96)00172-X

M3 - Article

AN - SCOPUS:0030577306

SN - 0020-0190

VL - 60

SP - 243

EP - 248

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -