Network reliability and acyclic orientations

Publisher Website
Google Scholar
Abstract
Let G = (V, E) be an undirected graph with V = n perfectly reliable vertices and E = m edges that work with probability pe and fail with probability qe for all e /in E. The network reliability problem considered here is to calculate RK[G] = Prob [there exists a path of working edges between every pair of a set K of k vertices]. Backtrack algorithms for this problem are presented. The complexity of these algorithms is discussed when applied to the all‐terminal network reliability problem where K = V. Strategies are presented which minimize the size of the search structures generated. The main theorems state that when these strategies are used, the size of the search structures may be measured by counting spanning trees or acyclic orientations.

This publication has 14 references indexed in Scilit: