RELIABILITY COVERING PROBLEMS

This paper studies the reliability covering problem, in which given routes provide 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 and 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.