Randomized and deterministic algorithms for network coding problems in wireless networks

• We give randomized algorithms for both the unicast and multicast network code completion problem over a fixed finite field.
• The related problem of fixable pairs is introduced.
• A sufficient condition is given for a set of pairs to be fixable.
• Applications for both problems in wireless and heterogeneous networks for capacity characterization.

Network coding is a method for information transmission in a network, based on the idea of enabling internal nodes to forward a function of the incoming messages, typically a linear combination. In this paper we discuss generalizations of the network coding problem with additional constraints on the coding functions called network code completion problem, NCCP. We give both randomized and deterministic algorithms for maximum throughput-achieving network code construction for the NCCP in the multicast case. We also introduce the related problem of fixable pairs, investigating when a certain subset of coding coefficients in the linear combination functions can be fixed to arbitrary non-zero values such that the network code can always be completed to achieve maximum throughput. We give a sufficient condition for a set of coding coefficients to be fixable. For both problems we present applications in different wireless and heterogeneous network models.