Finding the anti-block vital edge of a shortest path between two nodes

Let P-G (s,t) denote a shortest path between two nodes s and t in an undirected graph G with nonnegative edge weights. A detour at a node u epsilon P-G (s,t) = (s, ... , u, v, ... , t) is defined as a shortest path PG-e (u,t) from u to t which does not make use of (u,v). In this paper, we focus on the problem of finding an edge e = (u, v) epsilon P-G (s,t) whose removal produces a detour at node u such that the ratio of the length of PG-e (u,t) to the length of P-G (u,t) is maximum. We define such an edge as an anti-block vital edge (AVE for short), and show that this problem can be solved in O(mn) time, where n and m denote the number of nodes and edges in the graph, respectively. Some applications of the AVE for two special traffic networks are shown.