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

Sven Venema, Hong Shen, Francis Suraweera

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Citation (Scopus)

## Abstract

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.

Original language English 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 Jose Rolim Springer Verlag 464-471 8 3540643591, 9783540643593 https://doi.org/10.1007/3-540-64359-1_720 Published - 1998 Yes 10 Workshops held in conjunction with 12th International Parallel Symposium and 9th Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998 - Orlando, United StatesDuration: 30 Mar 1998 → 3 Apr 1998

### Publication series

Name Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 1388 0302-9743 1611-3349

### Conference

Conference 10 Workshops held in conjunction with 12th International Parallel Symposium and 9th Symposium on Parallel and Distributed Processing, IPPS/SPDP 1998 United States Orlando 30/03/98 → 3/04/98

## Fingerprint

Dive into the research topics of 'NC algorithms for the single most vital edge problem with respect to all pairs shortest paths'. Together they form a unique fingerprint.