Polynomial time algorithms for network code construction
- Sidharth Jaggi ,
- Peter Sanders ,
- Philip A. Chou ,
- Michelle Effros ,
- Sebastian Egner ,
- Kamal Jain ,
- Ludo M. G. M. Tolhuizen
IEEE Trans. Information Theory |
The famous max-flow min-cut theorem states that a source node can send information through a network (V,E) to a sink node 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.
© 2005 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.