Finding the Detour-Critical Node of the Shortest Path in Communication Networks

摘要：

In this paper, we present an interesting variant of the most vital node (MVN) problem of the shortest path in term of real time, which focus on finding the node vi ∈ PG(s,t) whose removal results in a detour at vi-1 such that the length of PG-vi(vi-1,t) minus the length of PG(vi-1,t) is the maximum. We call such a node the detour-critical node (DCN). This paper shows that the DCN problem can be solved in O(n3) time, where n denotes the number of nodes in graph. Finally, we give a numerical result of communication networks, which demonstrates that the DCN problem focuses on a real time process and has more practical application.

作者: Huahai Yan Yiwei Fang Tao Gu

作者单位: normalsize School of Management Xian Jiaotong University Xian, 710049, P.R. China School of Management Xian Jiaotong University Xian, 710049, P.R. China

会议类型: 国际会议

会议名称: 第三届国际脉冲动力系统及应用学术会议

会议地点: 青岛

会议语种:英文

在线出版日期: 2006-07-21（万方平台首次上网日期，不代表论文的发表时间）