Flow in networks with random capacities
- 1 January 1982
- journal article
- research article
- Published by Taylor & Francis in Stochastics
- Vol. 7 (3) , 205-229
- https://doi.org/10.1080/17442508208833219
Abstract
We study the problem of finding the maximum flow through a capacitated network in which the set of capacities is a collection of independent random variables, drawn from some known distribution. We find limit theorems when the underlying graph is either a branching tree or a complete graph. Finally, we discuss the difficulty of the problem of finding the expected maximum flow, using the language of computational complexity, and propose an easy approximate solution to the closely related reliability problem.Keywords
This publication has 9 references indexed in Scilit:
- Percolation theory and its ramificationsContemporary Physics, 1980
- Computational Complexity of Probabilistic Turing MachinesSIAM Journal on Computing, 1977
- On the difference between one and manyPublished by Springer Nature ,1977
- Subadditive Ergodic TheoryThe Annals of Probability, 1973
- Transportation networks with random arc capacitiesRevue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle, 1972
- First-Passage PercolationJournal of the Royal Statistical Society Series B: Statistical Methodology, 1966
- The Theory of Branching ProcessesPublished by Springer Nature ,1963
- On Deviations of the Sample MeanThe Annals of Mathematical Statistics, 1960
- Percolation processesMathematical Proceedings of the Cambridge Philosophical Society, 1957