Nowy algorytm do szybkiego obliczania niezawodności sieci.

Network reliability analysis of complex system (including computer, telecomunication, transportation networks or electric networks has been a subject of intensive research for a long time. The problem of network reliability analysis using connectivity based reliability measures is considered in this paper. Such measures are justified since most networks employ dynamic routing so that trafic can be rerouted around failed links as long as a network remains connected. A propbabilistic undirected graph G=(V, E) with a distinguished subset of vertices K is used to a model K. The problem of computing K-terminal reliability of a network with a general structure is known to be NP-hard. It means that it is unlikely that there exists an algorithm which will find exactly optimal solution to all instances of the problem in time which is polynomial in the size of the imput. A new algorithm utilising the cache technique which is a modified technique of dynamic programming and suitable heuristic strategies of preserving labels order and problem decomposition have been presented in this paper. The algorythm has been implemented and has achived excellent performances.