• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>2012 International Symposium on Information Theory and its Applications. >A coding theoretic approach for evaluating accumulate distribution on minimum cut capacity of weighted random graphs
【24h】

A coding theoretic approach for evaluating accumulate distribution on minimum cut capacity of weighted random graphs

机译：一种评估加权随机图最小割容量上的累积分布的编码理论方法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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ős-Ré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.
机译：定向网络的多播容量与s-t最大流量密切相关，后者由于最大流量最小割定理而等于s-t最小割容量。如果网络的拓扑结构（或链路容量）是动态变化的或具有随机性质，那么预测最大流量的统计属性并不是一件容易的事。在本文中，我们提出了一种编码理论方法，用于评估加权随机图的最小割容量的累积分布。我们方法的主要特征是利用图的剪切空间和列权值为2的二进制LDGM（低密度生成器矩阵）代码之间的对应关系。本文中处理的图集合是Erdős- Rényi随机图合奏。我们工作的主要贡献是最小切割能力的累积分布的组合下界。从一些计算机实验中，可以观察到，此处导出的下限反映了最小切割能力的实际统计行为。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号