Comparison of old and new algorithms for s,t -network reliability
Date
2020-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University.
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.
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.
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.
Description
Thesis (MSc)--Stellenbosch University, 2020.
Keywords
Computer networks -- Reliability, Algorithms, s,t-network, Networks (Mathematics) -- Reliability, UCTD