Study on the multicommodity reliability of a capacitated-flow network

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

47 Scopus citations


Traditionally, many researchers solved the multicommodity maximum flow problem by assuming that the arcs of the flow network are deterministic. When the arcs are stochastic (i.e., the capacity of each arc has several values), this article studies how to calculate the probability that a capacitated-flow network with a unique source node satisfies a demand (d1, d2,..., dp) at the unique sink node, where dk is the demand of commodity k. Such a probability is named the multicommodity reliability and is dependent on capacities of arcs. One solution procedure is proposed to evaluate the multicommodity reliability, which includes two parts: an algorithm to generate all (d1, d2,...,dp)MPs and a method to calculate the multicommodity reliability in terms of (d1, d2,..., dp)-MPs. Two illustrative examples are given.

Original languageEnglish
Pages (from-to)255-264
Number of pages10
JournalComputers and Mathematics with Applications
Issue number1-2
StatePublished - 1 Jul 2001


  • Capacitated-flow network
  • Demand
  • Minimal path
  • Multicommodity reliability

Fingerprint Dive into the research topics of 'Study on the multicommodity reliability of a capacitated-flow network'. Together they form a unique fingerprint.

Cite this