Inclusion-exclusion and network reliability (Q1128362)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Inclusion-exclusion and network reliability |
scientific article |
Statements
Inclusion-exclusion and network reliability (English)
0 references
11 August 1998
0 references
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.
0 references
\(k\)-out-of-\(n\) systems
0 references
inclusion-exclusion principle
0 references
network reliability
0 references