Finding the most vital node of a shortest path

✍ Scribed by Enrico Nardelli; Guido Proietti; Peter Widmayer

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 171 KB
• Volume: 296
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00438-3

✦ Synopsis

In an undirected, 2-node connected graph G = (V; E) with positive real edge lengths, the distance between any two nodes r and s is the length of a shortest path between r and s in G. The removal of a node and its incident edges from G may increase the distance from r to s. A most vital node of a given shortest path from r to s is a node (other than r and s) whose removal from G results in the largest increase of the distance from r to s. In the past, the problem of ÿnding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will a ect network e ciency the most. In this paper, we show that this problem can be solved in O(m+n log n) time and O(m) space, where m and n denote the number of edges and the number of nodes in G.