A deterministic polynomialtime algorithm for constructing a multicast coding scheme for linear deterministic relay networks
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
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 polynomialtime versions of our algorithm and show that for a network with g destinations, our deterministic algorithm can achieve the capacity in log(g + 1) uses of the network.
