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

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.