This thesis investigates the reliability of directed networks. Our assumption in these network models will be that the nodes always work and the arcs operate independently with a given probability p. For a digraph D(E, V) the strongly connected reliability is the probability that there exists a path from any node vi ∈ V to any other node vj ∈ V. An efficient algorithm to compute the strongly connected reliability of complete digraphs is provided. We explore some bounds of strongly connected reliability of general digraphs. For all digraphs with n vertices and m edges (where m is greater or equal to n) in which parallel arcs are allowed, we will prove there exists optimal (i.e. uniformly most reliable) ones and give an optimal topology. |