• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Annual Allerton Conference on Communication, Control, and Computing; 20040929-1001; Monticello,IL(US) >A Unification of Edmonds' Graph Theorem and Ahlswede etc's Network Coding Theorem
【24h】

A Unification of Edmonds' Graph Theorem and Ahlswede etc's Network Coding Theorem

机译：Edmonds图定理和Ahlswede等人的网络编码定理的统一

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

摘要

The multicast capacity is the maximum rate that a sender can communicate common information to a set of receivers in a network. A fundamental theorem in graph theory by Edmonds showed the broadcast capacity from a sender to all other nodes can be achieved by routing along multiple trees. Recently, Ahlswede etc established that the multicast capacity can be achieved by performing network coding. In this paper, we present a statement that unifies Edmonds' Theorem and Ahlswede etc's Theorem: the multicast capacity can be achieved by performing conventional routing on non-Steiner edges (edges entering receivers) and network coding on Steiner edges. We establish this result by constructively proving a graph theoretic theorem: all non-Steiner edges can be hardwired while preserving the required connectivity from the sender to each receiver. Hardwiring an edge means restricting it to connect with at most one of its predecessor edges.
机译：多播容量是发送方可以将公共信息传递给网络中一组接收方的最大速率。 Edmonds在图论中的一个基本定理表明，从发送方到所有其他节点的广播容量可以通过沿着多棵树进行路由来实现。最近，Ahlswede等人确定可以通过执行网络编码来实现多播容量。在本文中，我们提出一条声明，将Edmonds定理和Ahlswede等定理统一起来：多播容量可以通过在非Steiner边缘（进入接收器的边缘）进行常规路由，并在Steiner边缘进行网络编码来实现。我们通过构造性地证明图论定理来建立此结果：所有非Steiner边都可以硬连线，同时保留从发送方到每个接收方的所需连接性。硬连接边缘意味着限制其最多与其前任边缘之一连接。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号