I. Introduction
Each arc of a binary-state network has good/bad states. The network reliability, which is the probability that source communicates with sink , can be computed in terms of minimal paths (MPs) or minimal cuts (MCs) [9]. An MP is an ordered sequence of arcs from to that has no cycle. Note that an MP is different from the so-called minimum path. The latter one is a path with minimum cost whenever the arc contains the cost attribute. An MC is a cut whose proper subsets are no longer cuts. The network reliability can be treated as a performance index to measure the quality level for a real-life system with supply–demand character. Aggarwal et al. [3] extended the reliability problem to the node failure case. They proposed the concept that the failure of a node implies the failure of arcs incident from it. Using this concept, the original network with node failure can be modified to be a conventional network with perfect nodes.