Evaluating network reliability and 2-edge-connected reliability in linear time for bounded pathwidth graphs

This paper presents a decomposition method fur computing the 2-edge-connect ed reliability of undirected networks. This reliability is defined as the p robability that all the vertices of a given graph G are 2-edge-connected, w hen edges fail independently with known probabilities. The principle of thi s method was introduced by Rosenthal in 1977 [1]. For the all terminal reli ability problem it consists in enumerating specific state classes of some s ubnetworks. These classes are represented by the partitions of the boundary sets. For the 2-edge-connected reliability problem these classes are repre sented by labeled forests whose nodes are the partition blocks and some "un identified" blocks. Our implementation uses a vertex linear ordering. The c omputational complexity depends on the number of classes, which depends on the vertex separation number of a given vertex linear ordering. Our computa tional results show the efficiency of this method when the vertex separatio n number is smaller than 7.