Reliability of k separate minimal paths under both time and budget constraints

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


To minimize transmission time, the quickest path problem arises to find a path which sends a given amount of data from the unique source to the unique sink. Two deterministic attributes are involved in this problem: the capacity, and the lead time. However, in many real-life networks such as computer systems, or telecommunication systems, the arc capacity should be multistate due to failure, maintenance, and other such conditions. Such a network is named a multistate flow network, and the minimum transmission time is thus not fixed. We modify the quickest path problem to a multistate case. The new problem is to evaluate the probability that d units of data can be transmitted from the unique source to the unique sink under both the time, and budget constraints. In particular, the data are transmitted through k separate minimal paths simultaneously. Such a probability is named system reliability. An efficient algorithm is proposed to generate all minimal system states fulfilling the demand, time, and budget constraints. The system reliability is subsequently computed in terms of such system states. The optimal k minimal paths with the highest system reliability can further be obtained.

Original languageEnglish
Article number5373950
Pages (from-to)183-190
Number of pages8
JournalIEEE Transactions on Reliability
Issue number1
StatePublished - 12 Jan 2010


  • Budget constraint
  • K minimal paths
  • Multistate flow network
  • Quickest path
  • Time constraint

Fingerprint Dive into the research topics of 'Reliability of k separate minimal paths under both time and budget constraints'. Together they form a unique fingerprint.

Cite this