An Analysis on Minimum S-T Cut Capacity of Random Graphs With Specified Degree Distribution
The capacity (or maximum flow) of an uni-cast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, the authors present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of weighted graphs with arbitrary specified degree distribution.