We investigate network coding in star networks with multiple unicast sessions. We use entropy arguments to upper bound the simultaneous rates of communication among the different nodes in the network and prove that in many cases, the optimal network code is related to the combinatorial optimization problem of finding the maximum number of edge disjoint cycles in the demand graph of the network. Finally, we propose a polynomial time algorithm with linear binary operations that achieves the capacity in many cases.
name of conference
2008 IEEE International Symposium on Information Theory - ISIT