Polynomial time algorithms for network information flow

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
reencode the information they receive. However, so far it was not
known how to construct such coding schemes efficiently. We give
polynomial time algorithms for solving this problem. We additionally
underline the potential benefit of coding by showing that multicasting
without coding sometimes only allows a rate that is a factor
$\Omega(\log |V|)$ smaller.