Premium
Characterizing stochastic flow networks using the monte carlo method
Author(s) -
Alexopoulos Christos,
Fishman George S.
Publication year - 1991
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230210706
Subject(s) - monte carlo method , mathematics , node (physics) , upper and lower bounds , flow network , flow (mathematics) , set (abstract data type) , sampling (signal processing) , function (biology) , algorithm , combinatorics , discrete mathematics , mathematical optimization , computer science , statistics , filter (signal processing) , geometry , mathematical analysis , structural engineering , evolutionary biology , engineering , computer vision , biology , programming language
Consider a flow network G = (,ℰ) with node set and arc set ℰ = {1, …, e }. Assume that the nodes do not restrict flow transmission and the arcs have random, discrete and independent capacities B 1 , …, B e , and let B = {B 1 , …, B e } . Also, let s and t be a pair of nodes in , let Λ( B ) denote the value of a maximum s–t flow, and let Γ denote a set of s–t cuts. This work describes a highly efficient Monte Carlo sampling plan for estimating the probability that l < Λ( B ) ⩽ u , the probability that a cut in Γ is critical and l < Λ( B ) ⩽ u , and the probability that a cut in Γ is critical, given that l < Λ( B ) ⩽ u . The proposed method takes advantage of an easily computed upper bound on the probability that l < Λ( B ) ⩽ u , which is a function of both l and u to gain its computational advantage. The article also describes techniques for computing confidence intervals that are valid for any sample size. Algorithms for implementing the proposed sampling experiment are included, and an example illustrates the efficiency of the proposed method.