Reliability covering problems

Networks - Tập 21 Số 3 - Trang 345-357 - 1991
Michael O. Ball1, J. Scott Provan2, Douglas R. Shier3
1College of Business and Management, University of Maryland, College Park, Maryland 20742
2Department of Operations Research, University of North Carolina, Chapel Hill, North Carolina 27599
3Department of Mathematics, College of William & Mary, Williamsburg, Virginia 23185

Tóm tắt

AbstractThis paper studies the reliability covering problem, in which given routes provides service to various stops (e.g., of a transit system). If the routes are subject to failure, it is desired to find the probability that all stops will be covered by an operating route. It is shown that this problem is NP‐hard even when routes are defined with respect to an underlying tree. Polynomially solvable cases are developed when some additional structure is imposed on the routes of a tree: e.g., when the routes are directed paths of a rooted directed tree. These cases generalize reliability computations for consecutive k‐out‐of‐n systems as well as the extensions to consecutively connected systems studied by Shanthikumar and by Hwang and Yao.

Từ khóa


Tài liệu tham khảo

10.1287/opre.32.3.478

10.1109/TR.1986.4335422

10.1287/opre.36.5.703

Barlow R. E., 1981, Statistical Theory of Reliability and Life Testing

Garey M. R., 1979, Computers and Intractability: A Guide to the Theory of NP‐Completeness

Grätzer G., 1971, Lattice Theory

10.1109/24.46467

Lawler E. L., 1976, Combinatorial Optimization: Networks and Matroids

10.1287/opre.32.3.516

10.1109/TR.1987.5222467

10.1109/24.3711

Shier D. R., 1988, Applications of Discrete Mathematics, 135

10.1137/0208032

D. K.Wagner personal communication.

10.1109/TCOM.1972.1091214

Thông tin
Thông tin xuất bản

Networks

Tập 21 Số 3

345-357

Thông tin tác giả