A Max-Flow/Min-Cut Algorithm for Linear Deterministic Relay Networks Academic Article

abstract

• The linear deterministic model of relay networks (LDRN) is a generalization of the traditional directed network model which has become popular in the study of the flow of information over wireless communication networks. The max-flow/min-cut theorem for a multicast session over a directed network has been extended to this wireless relay model. The result was first proved by a random coding scheme over large blocks of transmitted signals. In this paper, in the special case of a unicast session, a simple capacity-achieving transmission scheme for LDRN which codes over one symbol of information at each use of the network is obtained by a connection to the submodular flow problem and through the application of tools from matroid theory and submodular optimization theory. Polynomial-time algorithms for calculating the capacity of the network and the optimal coding scheme are implied by our analysis. 2011 IEEE.

authors

• Savari, Serap

published proceedings

• IEEE TRANSACTIONS ON INFORMATION THEORY

author list (cited authors)

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

citation count

• 11

complete list of authors

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

publication date

• May 2011

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• IEEE TRANSACTIONS ON INFORMATION THEORY  Journal

keywords

• Flow Scheme
• Linear Deterministic Relay Network
• Max-flow Min-cut
• Network Coding
• Relay Network

Digital Object Identifier (DOI)

• 10.1109/TIT.2011.2120250

start page

• 3005

end page

• 3015

volume

• 57

issue

• 5

URL

• http://dx.doi.org/10.1109/tit.2011.2120250