from cs.IT updates on arXiv.org http://arxiv.org/abs/1301.7542

The capacity (or maximum flow) of an unicast 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, we 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. The main contribution of our work is a

lower bound for the accumulate distribution of the minimum s-t cut capacity.

From some computer experiments, it is observed that the lower bound derived

here reflects the actual statistical behavior of the minimum s-t cut capacity

of random graphs with specified degrees.