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

✍ Scribed by Sven Venema; Hong Shen; Francis Suraweera

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 537 KB
• Volume: 60
• Category: Article
• ISSN: 0020-0190
• DOI: 10.1016/s0020-0190(96)00172-x

✦ Synopsis

For a weighted, undirected graph G = (YE), 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(ma(m,n)), where n =I V I, m =I E 1, and LY(I~Z,II) 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 0( log n) time using m processors and O(m) space on the CRCW PRAM, in 0( log n) time using mn/ log n CREW processors and 0( m + n logm) space, and in 0( logn) time using mn/ logn EREW processors and 0( mn) space, respectively.

These are the first NC algorithms for solving this problem on the PRAM.