Comparison of old and new algorithms to compute the \(s,t\)-network reliability

Suppose \(G\) is a graph (= network) with two specified nodes \(s\) (the source) and \(t\) (the terminal). Further the edges of \(G\) are assumed to be operational with fixed (and independent) probability \(p\). Then the \(s,t\)- network reliability is defined as the probability \(nr(G)\) (which is a polynomial in \(p\)) of an operational path connecting \(s\) and \(t\). Calculating \(nr(G)\) is known to to be #P-complete. In this thesis we present some old techniques which have existed since the 1950’s, as well as four new algorithms for calculating \(nr(G)\). Because these algorithms are all coded in Mathematica as a common platform, they can be compared in a fair way.