Computer Science – Information Theory
Scientific paper
2012-02-04
Computer Science
Information Theory
5 pages, 2 figures, submitted to IEEE ISIT 2012
Scientific paper
The multicast capacity of a directed network is closely related to the $s$-$t$ maximum flow, which is equal to the $s$-$t$ minimum cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or have stochastic nature, it is not so trivial to predict statistical properties on the maximum flow. In this paper, we present a coding theoretic approach for evaluating the accumulate distribution of the minimum cut capacity of weighted random graphs. The main feature of our approach is to utilize the correspondence between the cut space of a graph and a binary LDGM (low-density generator-matrix) code with column weight 2. The graph ensemble treated in the paper is a weighted version of Erd\H{o}s-R\'{e}nyi random graph ensemble. The main contribution of our work is a combinatorial lower bound for the accumulate distribution of the minimum cut capacity. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum cut capacity.
Fujii Yuki
Wadayama Tadashi
No associations
LandOfFree
A Coding Theoretic Approach for Evaluating Accumulate Distribution on Minimum Cut Capacity of Weighted Random Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Coding Theoretic Approach for Evaluating Accumulate Distribution on Minimum Cut Capacity of Weighted Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Coding Theoretic Approach for Evaluating Accumulate Distribution on Minimum Cut Capacity of Weighted Random Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-330136