# (Reliability of Network Topologies, ReNeT)

Heidtmann, 1997,  developed an algorithm to compute the probability that the nodes of a subset of all nodes of a given network topology are connected by decomposing this event into a union of events which are disjoint and whose probabilities can be sumed up. The advantage of this method is that it produces much less disjoint terms than other methods and that it is therefore much more effective (For a comparison with other methods see ReNeTComp).

Xiang developed an applet to demonstrate that algorithm. You will be able to input your network model by drawing a graph and defining the probability of every edge of the network. The network will be firstly reduced by eliminating serial and parallel edges and then the reduced network will be decomposed with Heidtmann's method. Finally the reliability of the network (i.e. the probability the nodes of a subset K of all network nodes are connected) will be calculated and output.

Heidtmann's algorithm:
(for monoton systems only)

Procedure HEIDTMANN-ZERLEGUNG(I(0),I(1),...,I(k),i)
begin
if i=k
then output I(0),I(1),...,I(k-1)
else
if \$ l, 0<l<i and {}Ì I(l)Í Ii
then HEIDTMANN-ZERLEGUNG(I(0),I(1),...,I(k),i+1)
else
begin
for all l=0 upto k, HI(l)=I(l)
for all l=1 upto i-1
begin
HI(l)=I(l)Ç Ii
if HI(l)¹ {} then
HEIDTMANN-ZERLEGUNG(HI(0),HI(1),...,HI(k),i+1)
HI(l)=I(l)-Ii
HI(0)=HI(0)È (I(l)Ç Ii)
end
i-1
HI(i)= Ii-È I(l)
l=0

if HI(i)¹ {} then
begin
for all l=1 upto i-1, HI(l)=HI(l)-HI(i)
HEIDTMANN-ZERLEGUNG(HI(0),HI(1),...,HI(k),i+1)
end
end
end