Enumeration of the minimal node cutsets based on necessary minimal paths

Abstract

Reliability evaluation is an important research field for a complex network. The most popular methods for such evaluation often use Minimal Cuts (MC) or Minimal paths (MP). Nonetheless, few algorithms address the issue of the enumeration of all minimal cut sets from the source node s to the terminal node t when only the nodes of the network are subject to random failures. This paper presents an effective algorithm which enumerates all minimal node cuts sets of a network. The proposed algorithm runs in two steps: The first one is used to generate a subset of paths, called necessary minimal paths, instead of all minimal paths. Whereas, the second step stands to build all minimal cutsets from the necessary minimal paths.