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 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 (g+1) uses of the network and has the fastest construction time among algorithms for this problem. 1963-2012 IEEE.

authors

• Savari, Serap

published proceedings

• IEEE TRANSACTIONS ON INFORMATION THEORY

author list (cited authors)

• Yazdi, S., & Savari, S. A.

citation count

• 2

complete list of authors

• Yazdi, SM Sadegh Tabatabaei||Savari, Serap A

publication date

• January 2013

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE TRANSACTIONS ON INFORMATION THEORY  Journal

keywords

• Linear Deterministic Network
• Multicast Session
• Network Coding
• Wireless Gaussian Network

Digital Object Identifier (DOI)

• 10.1109/TIT.2013.2273793

start page

• 7541

end page

• 7552

volume

• 59

issue

• 11