A new algorithm to generate d-minimal paths in a multistate flow network with noninteger arc capacities

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

23 Scopus citations


This article is mainly to study the reliability evaluation in terms of MPs (minimal paths) for a multistate flow network G in which the capacities of each arc are real numbers. The transportation system from the source node s to the sink node t is one of such typical networks. Given the system demand d from s to t and MPs in advance, an algorithm is proposed first to find out all lower boundary points of level d (namely d-MPs here). The system reliability which is the probability that the system flow satisfies the demand d can be calculated in terms of such d-MPs. One example is presented to illustrate how all its d-MPs are generated. The computational time complexity in the worst case and average cases for such an algorithm is presented.

Original languageEnglish
Pages (from-to)269-285
Number of pages17
JournalInternational Journal of Reliability, Quality and Safety Engineering
Issue number3
StatePublished - 1 Jan 1998


  • Capacity
  • Flow Network
  • Minimal Path
  • Multistate
  • Reliability
  • d-MP

Cite this