Comparison of old and new algorithms for s,t -network reliability
| dc.contributor.advisor | Wild, Marcel | en_ZA |
| dc.contributor.author | Zainabu, Simotwo Chepkirui Faith | en_ZA |
| dc.contributor.other | Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. | en_ZA |
| dc.date.accessioned | 2020-02-26T09:42:41Z | |
| dc.date.accessioned | 2020-04-28T12:27:37Z | |
| dc.date.available | 2020-02-26T09:42:41Z | |
| dc.date.available | 2020-04-28T12:27:37Z | |
| dc.date.issued | 2020-04 | |
| dc.description | Thesis (MSc)--Stellenbosch University, 2020. | en_ZA |
| dc.description.abstract | 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. | en_ZA |
| dc.description.abstract | AFRIKAANSE OPSOMMING: Netwerk betroubaarheid is die waarskynlikheid dat ’n operasionele pad die bron s met die terminale t verbind. In praktiese gevalle was die meeste probleme met netwerkbetroubaarheid #P-volledig. In hierdie tesis sal ons ’n aantal ou tegnieke wat sedert die vyftigerjare bestaan, sowel as nuwe algoritmes vir die berekening van netwerkbetroubaarheid in Mathematica kodeer. Op hierdie manier raak die algoritmes se werkverrigtings vergelykbaar. Ons kyk eers na die uitputtende enumeratiewe metode. Vervolgens verduidelik ons die serie-parallelle reduksie wat toegepas word in die stelling vir sametrekking-skrapping. Uiteindelik is ons ook in staat om vier nuwe metodes aan te bied. Die vergelyking is gebaseer op die SVE-tyd wat deur netwerke benodig word. Die resultate word aangebied in die vorm van grafieke en tabelle en ons demonstreer enkele voorbeelde van die algoritmes. | af_ZA |
| dc.description.version | Masters | en_ZA |
| dc.format.extent | xi, 59 pages | en_ZA |
| dc.identifier.uri | http://hdl.handle.net/10019.1/108246 | |
| dc.language.iso | en_ZA | en_ZA |
| dc.publisher | Stellenbosch : Stellenbosch University. | en_ZA |
| dc.rights.holder | Stellenbosch University. | en_ZA |
| dc.subject | Computer networks -- Reliability | en_ZA |
| dc.subject | Algorithms | en_ZA |
| dc.subject | s,t-network | en_ZA |
| dc.subject | Networks (Mathematics) -- Reliability | en_ZA |
| dc.subject | UCTD | |
| dc.title | Comparison of old and new algorithms for s,t -network reliability | en_ZA |
| dc.type | Thesis | en_ZA |