COMPUTING NETWORK RELIABILITY IN TIME POLYNOMIAL IN THE NUMBER OF CUTS

被引：77

作者：

PROVAN, JS

BALL, MO

机构：

[1] NBS, WASHINGTON, DC 20234 USA

[2] UNIV N CAROLINA, CHAPEL HILL, NC 27514 USA

[3] UNIV MARYLAND, COLLEGE PK, MD 20742 USA

来源：

OPERATIONS RESEARCH | 1984年 / 32卷 / 03期

关键词：

D O I：

10.1287/opre.32.3.516

中图分类号：

C93 [管理学];

学科分类号：

12 ; 1201 ; 1202 ; 120202 ;

摘要：

The authors present a new algorithm that computes the probability that there is an operating path from a node s to a node t in a stochastic network. The computation time of this algorithm is bounded by a polynomial in the number of (s,t)-cuts in the network. An examination is also made of the complexity of other connectedness reliability problems with respect to the number of cutsets and pathsets in the network. These problems are distinguished as either having algorithms that are polynomial in the number of such sets, or having no such algorithms unless P equals NP.

引用

页码：516 / 526

页数：11

共 17 条

[1]

Aho A., 1976, DESIGN ANAL COMPUTER

[2]

Ball M. O., 1979, Mathematics of Operations Research, V4, P132, DOI 10.1287/moor.4.2.132

[3] BOUNDS ON THE RELIABILITY POLYNOMIAL FOR SHELLABLE INDEPENDENCE SYSTEMS [J].