Finding the anti-block vital edge of a shortest path between two nodes |
| |
Authors: | Bing Su Qingchuan Xu Peng Xiao |
| |
Institution: | (1) School of Management, Xi’an JiaoTong University, Xi’an, Shaanxi, 710049, China;(2) The State Key Lab for Manufacturing Systems Engineering, Xi’an, Shaanxi, 710049, China |
| |
Abstract: | 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∈P
G
(s,t)=(s,…,u,v,…,t) is defined as a shortest path P
G−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)∈P
G
(s,t) whose removal produces a detour at node u such that the ratio of the length of P
G−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.
This research is supported by NSF of China under Grants 70471035, 70525004, 701210001 and 60736027, and PSF of China under
Grant 20060401003. |
| |
Keywords: | Edge failures Shortest path Anti-block vital edge |
本文献已被 SpringerLink 等数据库收录! |
|