| An analysis of the computational complexity of certain network reliability algorithms is performed. The networks are undirected graphs with functional vertices and reliable edges subject to independent failures. Network reliability is defined as the probability that a specified subset of vertices is connected. Evaluation of network reliability is necessary in the analysis and design of reliable systems. Although this class of problems is NP-hard, the relative efficiency of such asymptotically complex algorithms remains important. Among existing algorithms, a common approach is to decompose the problem into subproblems for which efficient reduction techniques are applicable. The simplest such decomposition-reduction scheme is the creation of subproblems having series and parallel modules by conditioning on the state of an edge. This edge decomposition procedure is easily implemented as a backtracking algorithm, and we seek the optimal edge selection strategy and the efficiency it achieves. The effects of other backtrack refinement procedures besides series and parallel reductions are investigated, and the relationships our decomposition approach have with the composition, Boolean algebra, and inclusion-exclusion approaches are discussed.;Under certain conditions, the computational requirements of a backtracking algorithm which implements edge decomposition with series and parallel reductions are determined by the size of the binary computational structure generated. We introduce a graph invariant called the domination and show that for any coherent problem, the minimal number of leaves in the computational structure equals the domination of the associated graph. Computational optimality is achieved, under these conditions, if and only if all subproblems created remain coherent. The domination has been shown to equal the number of certain acyclic orientations of the graph and also to equal a value of the chromatic polynomial.;Using an extension of series reduction we called degree-2 reduction, the all-terminal problem is made computationally equivalent to the simplest terminal-pair problem defined on the same graph. If the graph is nonseparable, the minimal number of leaves in the binary computational structure generated by edge decomposition with degree-2 and parallel reductions equals the minimal terminal-pair domination of the graph. Computational optimality is achieved, under these conditions, if and only if all subproblems created involve nonseparable graphs. Series, parallel and degree-2 reductions are special cases of modular representation. . . . (Author's abstract exceeds stipulated maximum length. Discontinued here with permission of author.) UMI... |
