A Unification of Network Coding and Routing
For a linear network code, the encoding profile is specified by, for every output channel of a node, the set of input channels whose symbols upon which the symbol on the output channel depends. For a given single-source network coding problem, it is of fundamental interest to characterize all feasible encoding profiles of a linear network code that achieves the max-flow min-cut bound. The authors obtain such a characterization through a refinement of the Jaggi-Sanders algorithm. The refined algorithm also provides sharper bounds on the required field size when the network is given. Their results imply that the design of linear network codes with various constraints and optimization objectives is equivalent to arranging the maximum flows from the source node to the sink nodes.