Browsing by Author "Zainabu, Simotwo Chepkirui Faith"
Now showing 1 - 1 of 1
Results Per Page
Sort Options
- ItemComparison of old and new algorithms for s,t -network reliability(Stellenbosch : Stellenbosch University., 2020-04) Zainabu, Simotwo Chepkirui Faith; Wild, Marcel; Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences.ENGLISH ABSTRACT: Network reliability is the probability of an operative path connecting the source s with the terminal t. s, t-network reliability problems have been proven 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 the network reliability. Because these algorithms are all coded in Mathematica as a common platform, they can be compared in a fair way. We first consider the exhaustive enumeration method. Then we explain in detail the series-parallel reduction which is applied in the contraction deletion algorithm. Let ps[i] and cs[i] be the number of cardinality i pathsets and cutsets respectively. It was long known that knowing these parameters yields the network reliability at once. Two algorithms of Wild (which more generally concern arbitrary set filters) can be used to calculate the numbers ps[i] and cs[i] more efficiently than previous approaches. The comparison is based on CPU time where several random networks have been tested. The results are presented in the form of graphs and tables and we demonstrate some of the algorithms by examples.