· · · Repository hosted by TU Delft Library



Home · About · Disclaimer ·
   Options
 
Type:
Year:

Polynomial Time Algorithms for Multicast Network Code Construction

Attachments

These file attachments have been under embargo and were made available to the public after the embargo was lifted on 9 November 2005.

Author: Jaggi, S. (California Inst. Technol. Passadena) · Sanders, P. (MPI Informatik, Saarbruecken) · Chou, P.A. (Microsoft Res. Redmond) · Effros, M. (California Inst. Technol. Passadena) · Egner, S. · Jain, K. (Microsoft Res. Redmond) · Tolhuizen, L.M.G.
Type:article
Date:2005-11-09
Embargo lifted:2005-11-09
Publisher: IEEE
Institution: Philips Research
Source:IEEE Transactions on Information Theory; authors version
Identifier: MS 23.258
Keywords: algorithms · communication networks · linear coding · multicasting
Rights: (c) IEEE

Abstract

The famous max-flow min-cut theorem states that a source node can send information through a network ( ) to a sink node at a rate determined by the min-cut separating and . 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 theachievable 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 fordesigning linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and tocodes that are tolerant to edge failures.

Content Viewer