期刊
THEORETICAL COMPUTER SCIENCE
卷 296, 期 1, 页码 167-177出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/S0304-3975(02)00438-3
关键词
network survivability; shortest path; node vitality; mechanism design
In an undirected, 2-node connected graph G = (VE) 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 finding 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 affect network efficiency the most. In this paper, we show that this problem can be solved in O(m + nlogn) time and O(m) space, where m and n denote the number of. edges and the number of nodes in G. (C) 2002 Elsevier Science B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据