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
      0 references
      0 references
      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 references
      0 references
      0 references
      0 references
      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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references