An outer bound for multisource multisink network coding with minimum cost consideration

摘要

The max-flow min-cut bound is a fundamental result in the theory of communication networks, which characterizes the optimal throughput for a point-to-point communication network. The recent work of Ahlswede et al. extended it to single-source multisink multicast networks and Li et al. proved that this bound can be achieved by linear codes. Following this line, Erez and Feder as well as Ngai and Yeung proved that the max-flow min-cut bound remains tight in single-source two-sink nonmulticast networks. But the max-flow min-cut bound is in general quite loose (see Yeung, 2002). On the other hand, the admissible rate region of communication networks has been studied by Yeung and Zhang as well as Song and Yeung, but the bounds obtained by these authors are not explicit. In this work, we prove a new explicit outer bound for arbitrary multisource multisink networks and demonstrate its relation with the minimum cost network coding problem. We also determine the capacity region for a special class of three-layer networks.