On the Coding Advantage of Multiple Unicast Sessions in Undirected Graphs
Kamal Kishore Jain, Vijay V. Vazirani, Gideon Yuval · 2006
Li and Li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. Surprisingly enough, so far this conjecture could not be verified even for the simple network consisting of K3,2with four source-sink pairs. Using entropy calculus, we provide the first verification of the Li-Li conjecture for this network. We extend our bound to the case of an arbitrary directed bipartite network.