Network Reliability

Chapter 3

Path Sets Enumeration

The network reliability is usually concerned with the task of evaluating the terminal reliability or the probability of establishing communication between a set of specified nodes, which is often carried out using either path sets or cut sets of a probabilistic graph.

Although there is plethora of methods that exist to evaluate reliability measures, the most widely used technique in vogue still remains through path sets or cut sets and therefore enumeration of path sets (or spanning trees, or k-trees, let us call as path sets or success terms, in general) or its dual cut sets are the most fundamental step in evaluating the reliability measures of a network. Therefore, to make network reliability computation using path or cut sets competitively attractive, we must have an efficient method for enumerating path or cut sets as these path sets or cut sets are used to obtain system reliability expression in a compact form by employing SDP techniques.

The methods for enumerating path sets can broadly be divided into two categories:

a. By utilizing and exploitation of the information contained in the matrix representation of a network graph, and

b. Graph Traversal or Exhaustive Search Technique by using a suitable data structure containing the information of the network graph.

Generally, the methods based on first category do not require the knowledge advanced mathematics or graph theory.

Although there are several data structures available for a network ...