An Analysis on Minimum s-t Cut Capacity of Random Graphs with Specified Degree Distribution. (arXiv:1301.7542v1 [cs.IT])

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.

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s