Transmission reliability of k minimal paths within time threshold

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


The quickest path problem involving two attributes, the capacity and the lead time, is to find a single path with minimum transmission time. The capacity of each arc is assumed to be deterministic in this problem. However, in many practical networks such as computer networks, telecommunication networks, and logistics networks, each arc is multistate due to failure, maintenance, etc. Such a network is named a multistate flow network. Hence, both the transmission time to deliver data through a minimal path and the minimum transmission time through a multistate flow network are not fixed. In order to reduce the transmission time, the data can be transmitted through k minimal paths simultaneously. The purpose of this paper is to evaluate the probability that d units of data can be transmitted through k minimal paths within time threshold T. Such a probability is called the transmission reliability. A simple algorithm is proposed to generate all lower boundary points for (d, T), the minimal system states satisfying the demand within time threshold. The transmission reliability can be subsequently computed in terms of such points. Another algorithm is further proposed to find the optimal combination of k minimal paths with highest transmission reliability.

Original languageEnglish
Pages (from-to)1160-1165
Number of pages6
JournalComputers and Industrial Engineering
Issue number4
StatePublished - 1 Nov 2011


  • k minimal paths
  • Optimal combination
  • Quickest path
  • Reliability
  • Time threshold


Dive into the research topics of 'Transmission reliability of k minimal paths within time threshold'. Together they form a unique fingerprint.

Cite this