Polyhedral Combinatorics and Network Reliability

Abstract
This paper studies the reliability of systems comprised of variables which must satisfy a set of linear equalities and nonnegativity constraints, and which are subject to random failure. A major example, which will be given special emphasis, is the reachability (source-to-all connectedness reliability) problem for stochastic networks. We show how properties of convex polyhedra, and their network counterparts, are useful in determining properties of the reliability polynomial for these systems. In particular, we show how recent results by Stanley and by Billera and Lee concerning the face numbers of convex polytopes and polyhedra can be applied to provide good upper and lower bounds on reliability in linear systems, and we apply these bounds in the network examples.

This publication has 0 references indexed in Scilit: