Premium
Reliability covering problems
Author(s) -
Ball M. O.,
Provan J. S.,
Shier D. R.
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210306
Subject(s) - reliability (semiconductor) , tree (set theory) , computer science , mathematical optimization , computation , directed graph , mathematics , combinatorics , algorithm , power (physics) , physics , quantum mechanics
This 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.