A Simple Improved Algorithm for (d, c)-MC Problem  
Author Majid Forghani-elahabad


Co-Author(s) Nelson Kagan


Abstract In a multistate flow network (MFN) with cost constraints, the network reliability at level (d,c) is the probability of transmitting at least d units of product from a source node to a destination node through the network within the cost of c, where d is a given demand value and c is a given budget. Several algorithms have been proposed in the literature in terms of minimal cuts (MCs) or minimal paths to assess the system reliability with or without cost constraints. By the way, considering the cost constraints is more realistic. Hence, here the problem of reliability evaluation of an MFN with cost constraint in terms of MCs is considered which is called the (d,c)-MC problem. Some techniques are presented to improve the solution, and accordingly a simple improved algorithm is proposed to address the problem. The algorithm is illustrated on a benchmark, and its time complexity is computed to show the efficiency of the proposed algorithm comparing to the available algorithms in the literature.


Keywords System reliability, Multistate flow network, Cost constraints, (d, c)-MC
    Article #:  24264
Proceedings ISSAT International Conference on Reliability and Quality in Design 2018
August 2-4, 2018 - Toronto, Ontario, Canada