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.