Polynomial time algorithms for network code construction

Sidharth Jaggi, Peter Sanders, Philip A. Chou, Michelle Effros, Sebastian Egner, Kamal Jain, and Ludo M. G. M. Tolhuizen


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.


Publication typeArticle
Published inIEEE Trans. Information Theory
PublisherInstitute of Electrical and Electronics Engineers, Inc.
> Publications > Polynomial time algorithms for network code construction