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 -