Constructing a Linear Network Code for Multicast Networks Based on Hypergraphs
Min Yang, Yuanyuan Yang · 2007
Network coding is a promising generalization of routing which allows a node to generate output messages by encoding its received messages. An important scenario where network coding offers unique advantages is a multicast network where a source node generates messages and multiple receivers collect the messages. In a multicast network, linear network codes are preferred due to its sufficiency and simplicity. In this paper, we propose a method to transform the linear coding problem to a graph theory problem. With the help of hypergraphs, we model the linear codes by constructing a pseudo-dual graph of the multicast network. A valid linear code is equal to a cover in the pseudo-dual graph satisfying some constraints. By iterative refinements, an eligible cover can be found in polynomial time. Moreover, this method can be readily applied to many minimum network coding problems as well.