期刊
NETWORKS
卷 60, 期 2, 页码 103-119出版社
WILEY
DOI: 10.1002/net.20464
关键词
critical node problem; tree; series-parallel graph; dynamic programming; polynomial-time algorithm
资金
- Air Force Office of Scientific Research [FA9550-08-1-0189]
- Defense Threat Reduction Agency [HDTRA1-10-1-0050]
We examine variants of the critical node problem on specially structured graphs, which aim to identify a subset of nodes whose removal will maximally disconnect the graph. These problems lie at the intersection of network interdiction and graph theory research and are relevant to several practical optimization problems. The two different connectivity metrics that we consider regard the number of maximal connected components (which we attempt to maximize) and the largest component size (which we attempt to minimize). We develop optimal polynomial-time dynamic programming algorithms for solving these problems on tree structures and on series-parallel graphs, corresponding to each graph-connectivity metric. We also extend our discussion by considering node deletion costs, node weights, and solving the problems on generalizations of tree structures. Finally, we demonstrate the computational efficacy of our approach on randomly generated graph instances. (c) 2011 Wiley Periodicals, Inc. NETWORKS, 2012
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据