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.

Provided by: Nagoya Institute of Technology Topic: Networking Date Added: Jan 2013 Format: PDF

Find By Topic