Characterizing stochastic flow networks using the monte carlo method (Q3984282)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 25954
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Characterizing stochastic flow networks using the monte carlo method |
scientific article; zbMATH DE number 25954 |
Statements
Characterizing stochastic flow networks using the monte carlo method (English)
0 references
27 June 1992
0 references
cuts and paths in graphs
0 references
stochastic flow networks
0 references
Monte Carlo method
0 references
water distribution networks
0 references
0.9105756878852844
0 references
0.8857056498527527
0 references
0.8594629168510437
0 references
The elements studied in the paper are stochastic flow networks composed of nodes and arcs and characterized by random, statistically independent, non-negative, integer valued capacities. The purpose is to determine an estimate for the probability that a flow value of the network between a source and a target node remains between certain lower and upper bounds. The time required for sampling, per replication and confidence intervals are also computed. Monte Carlo method is applied on upper and lower bounds in order to minimize the variation of the results. The upper and lower bounds are calculated using arc-disjoint paths and arc-disjoint cuts. The results are derived first for two-state (integer) capacities of arcs. For the multicapacity levels each arc is replaced with a number of new arcs connected in series with independent capacities with a certain distribution. This does not increase the number of arc-disjoint paths. The amount of time required to compute the upper bound (based on arc- disjoint cuts) grows significantly but remains polynomial. This means the algorithms proposed are clearly better than the NP-hard case of direct computation of the previously mentioned probability. The results are useful for example in the analysis of the reliability or critical points of water distribution networks. Some elements are derived from previous articles of the authors. May be a summary of the notations would ease the reading. There is a numeric example used by the authors to exemplify the difference between the crude Monte Carlo and the proposed method.
0 references