Inclusion-exclusion and network reliability (Q1128362): Difference between revisions

Summary: Based on a recent improvement of the inclusion-exclusion principle, we present a new approach to network reliability problems. In particular, we give a new proof of a result of \textit{D. R. Shier} [``Network reliability and algebraic structures'' (1991; Zbl 0729.90033), pp. 72-83, and in: Applications of discrete mathematics, 135-147 (1988; Zbl 0663.90034)], which expresses the reliability of a network as an alternating sum over chains in a semilattice, and a new proof of a result of \textit{J. S. Provan} and \textit{M. O. Ball} [Oper. Res. 32, 516-526 (1984; Zbl 0544.90034)], which provides an algorithm for computing network reliability in pseudopolynomial time. Moreover, some results on \(k\)-out-of-\(n\) systems are established.