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


  • 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.

published proceedings


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

  • January 2011