Full Text Available
Note: Clicking the button above will open the full text document at the original institutional repository in a new window.
Comparison of old and new algorithms for s,t -network reliability
Thesis (MSc)--Stellenbosch University, 2020.
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Language: | en_ZA |
| Published: |
Stellenbosch : Stellenbosch University.
2020
|
| Subjects: | |
| Tags: |
No Tags, Be the first to tag this record!
|
| _version_ | 1867613816833966080 |
|---|---|
| access_status_str | Open Access |
| author | Zainabu, Simotwo Chepkirui Faith |
| author2 | Wild, Marcel |
| author_browse | Wild, Marcel Zainabu, Simotwo Chepkirui Faith |
| author_facet | Wild, Marcel Zainabu, Simotwo Chepkirui Faith |
| author_sort | Zainabu, Simotwo Chepkirui Faith |
| collection | Thesis |
| dc_rights_str_mv | Stellenbosch University. |
| description | Thesis (MSc)--Stellenbosch University, 2020. |
| format | Thesis |
| id | oai:scholar.sun.ac.za:10019.1/108246 |
| institution | Stellenbosch University (South Africa) |
| language | en_ZA |
| last_indexed | 2026-06-10T12:42:09.814Z |
| license_str | Other — see source repository |
| provenance_str_mv | Harvested via OAI-PMH from SUNScholar — Stellenbosch University Repository |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| publisher | Stellenbosch : Stellenbosch University. |
| publisherStr | Stellenbosch : Stellenbosch University. |
| record_format | dspace |
| source_str | SUNScholar — Stellenbosch University Repository |
| spelling | oai:scholar.sun.ac.za:10019.1/108246 Comparison of old and new algorithms for s,t -network reliability Zainabu, Simotwo Chepkirui Faith Wild, Marcel Stellenbosch University. Faculty of Science. Dept. of Mathematical Sciences. Computer networks -- Reliability Algorithms s,t-network Networks (Mathematics) -- Reliability UCTD Thesis (MSc)--Stellenbosch University, 2020. 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. 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. Masters 2020-02-26T09:42:41Z 2020-04-28T12:27:37Z 2020-02-26T09:42:41Z 2020-04-28T12:27:37Z 2020-04 Thesis http://hdl.handle.net/10019.1/108246 en_ZA Stellenbosch University. xi, 59 pages application/pdf Stellenbosch : Stellenbosch University. |
| spellingShingle | Computer networks -- Reliability Algorithms s,t-network Networks (Mathematics) -- Reliability UCTD Zainabu, Simotwo Chepkirui Faith Comparison of old and new algorithms for s,t -network reliability |
| title | Comparison of old and new algorithms for s,t -network reliability |
| title_full | Comparison of old and new algorithms for s,t -network reliability |
| title_fullStr | Comparison of old and new algorithms for s,t -network reliability |
| title_full_unstemmed | Comparison of old and new algorithms for s,t -network reliability |
| title_short | Comparison of old and new algorithms for s,t -network reliability |
| title_sort | comparison of old and new algorithms for s t network reliability |
| topic | Computer networks -- Reliability Algorithms s,t-network Networks (Mathematics) -- Reliability UCTD |
| url | http://hdl.handle.net/10019.1/108246 |
| work_keys_str_mv | AT zainabusimotwochepkiruifaith comparisonofoldandnewalgorithmsforstnetworkreliability |