A Deterministic Polynomial-Time Algorithm for Constructing a Multicast Coding Scheme for Linear Deterministic Relay Networks

作者：Yazdi S M Sadegh Tabatabaei^*; Savari Serap A

来源：IEEE Transactions on Information Theory, 2013, 59(11): 7541-7552.

DOI：10.1109/TIT.2013.2273793

• Linear deterministic network
• multicast session
• network coding
• wireless Gaussian network

We propose a new way to construct a multicast coding scheme for linear deterministic relay networks. Our construction can be regarded as a generalization of the well-known multicast network coding scheme of Jaggi et al. to linear deterministic relay networks and is based on the notion of flow for a unicast session that was introduced by the authors in earlier work. We present randomized and deterministic polynomial-time versions of our algorithm and show that for a network with destinations, our deterministic algorithm can achieve the capacity in uses of the network and has the fastest construction time among algorithms for this problem.

• 出版日期2013-11