A Max-Flow/Min-Cut Algorithm for a Class of Wireless Networks
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
The linear deterministic model of relay channels 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 of Ford and Fulkerson has recently been extended to this wireless relay model. This result was first proved by a random coding scheme over large blocks of transmitted signals. We demonstrate the same result with a deterministic, polynomial-time algorithm which takes as input a single transmitted signal instead of a long block of signals. The max-flow/min-cut theorem of Ford and Fulkerson is related to a number of famous results in combinatorics including Hall's marriage theorem. Hall's marriage theorem is a special case of a well-known result in matroid theory and in transversal theory named the Rado-Hall theorem. We show that the max-flow/min-cut theorem for linear deterministic relay networks is connected to (1) a two-dimensional transversal theorem for block matrices which is a new application of the Rado-Hall theorem and (2) a combinatorial result on sequences of block matrices which is obtained through results in submodular optimization.
