Abstract

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.