|
On Search for all d-MCs in a Network Flow
|
M. Forghani-elahabad   , N. Mahdavi-Amiri * |
| Faculty of Mathematical Sciences, Sharif University of Technology, Tehran, Iran , nezamm@sina.sharif.edu |
|
|
Abstract: (27185 Views) |
| A number of problems in several areas such as power transmission and distribution, communication and transportation can be formulated as a stochastic-flow network (SFN). The system reliability of an SFN can be computed in terms of all the upper boundary points, called d-MinCuts (d-MCs). Several algorithms have been proposed to find all the d-MCs in an SFN. Here, some recent studies in the literature on search for all d-MCs are investigated. We show that some existing results and the corresponding algorithms are incorrect. Then, correct versions of the results are established. By modifying an incorrect algorithm, we also propose an improved algorithm. In addition, complexity results on a number of studies are shown to be erroneous and correct counts are provided. Finally, we present comparative numerical results in the sense of performance profile of Dolan and Moré showing the proposed algorithm to be more efficient than some existing algorithms. |
|
| Keywords: Reliability, Stochastic-flow network, Upper boundary points, Minimal cut (MC) |
|
|
Full-Text [PDF 801 kb]
(34623 Downloads)
|
Type of Study: Original |
Subject:
Discrete Optimization
Received: 2012/08/20 | Accepted: 2013/04/22 | Published: 2014/10/31
|
|
|
|
|
|
|
| Send email to the article author |
|
|
|
| Add your comments about this article |
|
|
|
