Stochastic flow networks via multiple paths under time threshold and budget constraint

Yi-Kuei Lin*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

This paper extends the quickest path problem to a stochastic flow network in which the capacity of each arc is variable. We mainly evaluate the system reliability that d units of data can be sent from the source to the sink under both time threshold T and budget B. In particular, the data are transmitted through multiple disjoint minimal paths simultaneously in order to reduce the transmission time. A simple algorithm is proposed to generate all lower boundary points for (d,T,B), and the system reliability can then be computed in terms of such points by utilizing a union of subsets. Computational complexity in both worst case and average cases show that the proposed algorithm can be executed efficiently.

Original languageEnglish
Pages (from-to)2629-2638
Number of pages10
JournalComputers and Mathematics with Applications
Volume62
Issue number6
DOIs
StatePublished - 1 Sep 2011

Keywords

  • Budget
  • Quickest path
  • Stochastic flow network
  • System state
  • Time threshold

Fingerprint Dive into the research topics of 'Stochastic flow networks via multiple paths under time threshold and budget constraint'. Together they form a unique fingerprint.

Cite this