Polynomial time algorithms for multicast network code construction
Polynomial time algorithms for multicast network code construction
复制标题
DOI：
10.1109/tit.2005.847712
复制
发表时间：
2005-06-01
影响因子：
2.5
通讯作者：
Tolhuizen, LMGA
中科院分区：
文献类型：
--
作者：
Jaggi, S;Sanders, P;Tolhuizen, LMGA
著名的最大流最小割定理指出，源节点S可以通过网络(V，E)以由分隔S和t的最小割所确定的速率向汇节点t发送信息。最近，已有研究表明，如果允许中间节点对其接收的信息进行重新编码，则对于多个汇点的组播也可以达到该速率。我们展示了一些网络的例子，在这些网络中，通过在中间节点进行编码而获得的可实现速率比不允许编码时的速率大得多。我们给出了设计单位容量边有向无圈图的线性码的确定性多项式时间算法和更快的随机化算法。我们将这些算法扩展到整数容量和容忍边故障的代码。
The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.