Date Added: May 2012
In this paper, some novel results on the encoding complexity of network coding and its relation with the network topology are reported. The encoding complexity in network coding is defined as the number of nodes which have to perform coding operations in order to achieve the multicast capacity. These nodes are referred to as coding points. Known results state that the number of coding points is cubic in the mincut and quadratic in the number of receivers. In this paper, the authors show, through extensive simulations and through analysis of these results, that the number of coding points tends to increase linearly in the min-cut and the number of receivers in random graphs.