A maximal flow method to search for d-MPs in stochastic-flow networks

Yi-Kuei Lin, Shin Guang Chen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


Since 1954, the maximal flow problems have gained much attention in the world. They are also extended to many other fields for applications. For example, the definition of a network reliability is just to evaluate the probability of a live connection between the source node and the sink node such that the maximal flow of the network is no less than the demand d. The popular methods in the literature to evaluate the network reliability are mostly through minimal paths (MP) or minimal cuts (MC) of the network. One of them is the three-stages method: (a) searching for all MPs/MCs; (b) searching for all d-MPs (the minimal system states for d via MP)/d-MCs (the maximal system states for d via MC); (c) calculating union probability from these d-MPs/d-MCs. We found that a creative innovation in solving the maximal flow problems may have benefits in the evaluation of network reliability. Based on this idea, this paper proposes a new approach to tackle the problem of searching for all d-MPs by given MPs. The comparisons with the well known algorithm are made for benchmarking. More complicated examples are also examined for illustrative purposes.

Original languageEnglish
Pages (from-to)119-125
Number of pages7
JournalJournal of Computational Science
StatePublished - 1 Sep 2017


  • Fast enumeration
  • Maximal flow
  • Minimal path
  • Network reliability
  • d-MPs

Fingerprint Dive into the research topics of 'A maximal flow method to search for d-MPs in stochastic-flow networks'. Together they form a unique fingerprint.

Cite this