Network reliability and the factoring theorem

A. Satyanarayana, Mark K. Chang

Networks · 1983 · 253 citations · 32 references

Concepts

TL;DR

Network reliability analysis seeks the probability that a specified vertex subset is connected, and Moskowitz’s factoring theorem expresses a graph’s reliability in terms of smaller graphs with one fewer vertex or edge. The paper introduces the domination invariant and presents an algorithm that guarantees optimal binary structure generation for efficient factoring theorem implementation. The recursion is represented by a binary structure whose leaves are reduced graphs; series and parallel edges are simplified by standard rules, and the complexity is governed by the number of leaves, with an optimal structure having the minimal leaves. The study proves that the optimal binary structure’s leaf count equals the graph’s domination, and recursive factoring yields an optimal structure precisely when each intermediate reduced graph has nonzero domination.

Abstract

Abstract In network reliability analysis, an important problem is to determine the probability that a specified subset of vertices in an undirected graph is connected. It is well known that, by using Moskowitz's factoring theorem, the reliability of a graph can be expressed in terms of the reliabilities of a graph with one fewer vertex and another with one fewer edge. The theorem can be applied recursively on the reduced graphs. The computations involved in this recursion can be represented by a binary structure such that its leaves correspond to reduced graphs whose reliabilities can be readily evaluated. In general, as the recursion progresses, series and parallel edges are created which can be reduced by using series and parallel rules of reliability assuming edges fail independently of each other. The computational complexity is a function of the number of leaves in the binary structure, and for a given graph, an optimal binary structure is the one with minimal number of leaves. In this article, a combinatorial invariant of a graph, called the domination, is established. Several important properties of the domination with regard to the topology of the graph are investigated. It is shown that for a given graph, the number of leaves in the optimal binary structure is equal to the domination of the graph and recursive application of the factoring theorem yields an optimal structure if and only if at each step the reduced graphs generated have nonzero dominations. Finally, an algorithm is presented that guarantees optimal binary structure generation and therefore an efficient implementation of the factoring theorem to compute the network reliability.

References

32