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:
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 ...