A Caltech Library Service

Polynomial time algorithms for multicast network code construction

Jaggi, Sidharth and Sanders, Peter and Chou, Philip A. and Effros, Michelle and Egner, Sebastian and Jain, Kamal and Tolhiuzen, Ludo M. G. M. (2005) Polynomial time algorithms for multicast network code construction. IEEE Transactions on Information Theory, 51 (6). pp. 1973-1982. ISSN 0018-9448. doi:10.1109/TIT.2005.847712.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. Manuscript received July 18, 2003; revised November 30, 2004. [Posted online: 2005-05-31] Most of this work was performed when S. Jaggi was a summer intern at Microsoft Research, Redmond, WA, and when P. Sanders was at MPI Informatik. The work of S. Jaggi and M. Effros was supported in part by a Microsoft Fellowship, the National Science Foundation under Grant CCR-0220039, and a grant from the Lee Center for Advanced Networking at Caltech. The work of P. Sanders was supported in part by DFGunder Grant SA 933/1-1. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Yokohama, Japan, June/July 2003 and at the SPAA 2003, San Diego, CA, June 2003. The authors would like to thank Rudolf Ahlswede, Ning Cai, Tracy Ho, Irit Katriel, Joerg Kliewer, Piotr Krysta, Anand Srivastav, Mandyam Aji Srinivas, and Berthold Vöcking for fruitful discussions, and the anonymous reviewers for many valuable comments concerning the presentation.
Subject Keywords:Communication networks, efficient algorithms, linear coding, multicasting rate maximization, network coding
Issue or Number:6
Record Number:CaltechAUTHORS:JAGieeetit05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1814
Deposited By: Archive Administrator
Deposited On:19 Feb 2006
Last Modified:08 Nov 2021 19:42

Repository Staff Only: item control page