An Analysis on Minimum s-t Cut Capacity of Random Graphs with Specified Degree Distribution
Abstrak
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.
Topik & Kata Kunci
Penulis (2)
Yuki Fujii
Tadashi Wadayama
Akses Cepat
- Tahun Terbit
- 2013
- Bahasa
- en
- Sumber Database
- arXiv
- Akses
- Open Access ✓