Time version of the shortest path problem in a stochastic-flow network

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticle

30 Scopus citations

Abstract

Many studies on hardware framework and routing policy are devoted to reducing the transmission time for a flow network. A time version of the shortest path problem thus arises to find a quickest path, which sends a given amount of data from the unique source to the unique sink with minimum transmission time. More specifically, the capacity of each arc in the flow network is assumed to be deterministic. However, in many real-life networks, such as computer systems, telecommunication systems, etc., the capacity of each arc should be stochastic due to failure, maintenance, etc. Such a network is named a stochastic-flow network. Hence, the minimum transmission time is not a fixed number. We extend the quickest path problem to evaluating the probability that d units of data can be sent under the time constraint T. Such a probability is named the system reliability. In particular, the data are transmitted through two minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all (d, T)-MPs and the system reliability can then be computed in terms of (d, T)-MPs. Moreover, the optimal pair of minimal paths with highest system reliability could be obtained.

Original languageEnglish
Pages (from-to)150-157
Number of pages8
JournalJournal of Computational and Applied Mathematics
Volume228
Issue number1
DOIs
StatePublished - 1 Jun 2009

Keywords

  • Quickest path
  • Shortest path
  • Stochastic-flow network
  • Time constraint
  • Two minimal paths

Fingerprint Dive into the research topics of 'Time version of the shortest path problem in a stochastic-flow network'. Together they form a unique fingerprint.

  • Cite this