Efficient solutions for finding vitality with respect to shortest paths

摘要

Let G = (V, E) be a connected, weighted, undirected graph such that |V| = n and |E| = m. Given a shortest path Pg (s, t) between a source node s and a sink node t in the graph G, computing the shortest path between source and sink without using a particular edge (or a particular node) in Pg(s, t) is called Replacement Shortest Path for that edge (or node). The Most Vital Edge (MVE) problem is to find an edge in Pg(s, t) whose removal results in the longest replacement shortest path. And the Most Vital Node (MVN) problem is to find a node in PG(s, t) whose removal results in the longest replacement shortest path. In this paper for the MVE problem we describe an O(m+m'a(m', n')) time algorithm (α represents Inverse Ackermann function) by constructing a smaller graph LG from G which we call Linear Graph, where n' and m' are the number of nodes and edges in LG respectively. Our algorithm will also suggest a replacement shortest path for every edge in Pg(s, t) without any additional time. For the MVN problem, with integer weights, we describe an O(mα(m, n)) time algorithm. Our algorithm will also suggest a replacement shortest path for every node in PG (s, t) without any additional time.