TY - GEN
T1 - NC algorithms for the single most vital edge problem with respect to all pairs shortest paths
AU - Venema, Sven
AU - Shen, Hong
AU - Suraweera, Francis
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1998.
PY - 1998
Y1 - 1998
N2 - For a weighted, undirected graph G = (V, E) where |V| = n and |E| = m, we examine the single most vital edge with respect to two measurements related to all-pairs shortest paths (APSP). The first measurement considers only the impact of the removal of a single edge from the APSP on the shortest distance between each vertex pair. The second considers the total weight of all the edges which make up the APSP, that is, calculate the sum of the distance between each vertex pair after the deletion of a tree edge. We give a sequential algorithm for this problem, and show how to obtain an NC algorithm running in O(log n) time using mn2 processors and O(mn2) space on the MINIMUM CRCW PRAM. Given the shortest distance between each pair of vertices u and v, the diameter of the graph is defined as the longest of these distances. The Most vital edge with respect to the diameter is the edge lying on such a u - v shortest path which when removed causes the greatest increase in the diameter. We show how to modify the above algorithm to solve this problem using the same time and number of processors. Both algorithms compare favourably with the straightforward solution which simply recalculates the all pairs shortest path information.
AB - For a weighted, undirected graph G = (V, E) where |V| = n and |E| = m, we examine the single most vital edge with respect to two measurements related to all-pairs shortest paths (APSP). The first measurement considers only the impact of the removal of a single edge from the APSP on the shortest distance between each vertex pair. The second considers the total weight of all the edges which make up the APSP, that is, calculate the sum of the distance between each vertex pair after the deletion of a tree edge. We give a sequential algorithm for this problem, and show how to obtain an NC algorithm running in O(log n) time using mn2 processors and O(mn2) space on the MINIMUM CRCW PRAM. Given the shortest distance between each pair of vertices u and v, the diameter of the graph is defined as the longest of these distances. The Most vital edge with respect to the diameter is the edge lying on such a u - v shortest path which when removed causes the greatest increase in the diameter. We show how to modify the above algorithm to solve this problem using the same time and number of processors. Both algorithms compare favourably with the straightforward solution which simply recalculates the all pairs shortest path information.
UR - http://www.scopus.com/inward/record.url?scp=84947484139&partnerID=8YFLogxK
U2 - 10.1007/3-540-64359-1_720
DO - 10.1007/3-540-64359-1_720
M3 - Conference contribution
AN - SCOPUS:84947484139
SN - 3540643591
SN - 9783540643593
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 464
EP - 471
BT - Parallel and Distributed Processing - 10 IPPS/SPDP 1998 Workshops Held in Conjunction with the 12th International Parallel Processing Symposium and 9th Symposium on Parallel and Distributed Processing, Proceedings
A2 - Rolim, Jose
PB - Springer Verlag
T2 - 10 Workshops held in conjunction with 12th International Parallel Symposium and 9th Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998
Y2 - 30 March 1998 through 3 April 1998
ER -