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

Abstract

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 $g$ destinations, our deterministic algorithm can achieve the capacity in $\lceil \log (g+1)\rceil$ uses of the network.

12 pages, 2 figures, submitted to CISS 2011

References in corpus (2)

• Approximate Capacity of Gaussian Relay Networks
• Algebraic Network Coding Approach to Deterministic Wireless Relay Networks