An Efficient Polynomial Time Algorithm for Robust Multicast Network Code Construction

For a single source multicast network with failed edges, a robust network code is given to achieve the network capacity by coding only at a subset of edges. Our algorithm provides shaper bounds on the required field size when failure patterns are given. The more required coding edges involved in the linear coding operation, the more computation it takes. The number of required coding edges is minimal in minimal multicast networks employing our algorithm.