Multiterminal resilience for series-parallel networks

被引：9

作者：

Farley, Toni R. ^{[1
]}

Colbourn, Charles J. ^{[1
]}

机构：

[1] Arizona State Univ, Tempe, AZ 85287 USA

来源：

NETWORKS | 2007年 / 50卷 / 02期

关键词：

network resilience; network reliability; series-parallel networks;

D O I：

10.1002/net.20186

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Network resilience measures the average two-terminal reliability (connectedness) of a network. Multiterminal resilience extends this measure to any k vertices; it is the average k-terminal reliability of a network. This generalizes two well-studied network connectedness measures. Calculating multiterminal resilience on general networks encompasses all-terminal reliability and thus is NP-hard. Multiterminal resilience is examined on undirected series-parallel networks, and an efficient (polynomial time) algorithm is developed for calculating the resilience for every k. Applications in mobile ad hoc and sensor networks are outlined. (C) 2007 Wiley Periodicals, Inc.

引用

页码：164 / 172

页数：9

共 17 条

[1]

ABOELFOTOH HMF, 1989, ORSA J COMPUTING, V1, P205

[2]

ABOELFOTOH HMF, 2007, IN PRESS INT J SENSO, V2

[3]

ABOELFOTOH HMF, 2006, P IEEE INT C COMM IC

[4] ON THE NONEXISTENCE OF UNIFORMLY OPTIMAL GRAPHS FOR PAIR-CONNECTED RELIABILITY [J].