An improved bound for multiple source-sink linear network coding
Munin Eamopas, Jittat Fakcharoenphol · 2011
This paper considers the linear network coding problem when there are k independent source-sink pairs. The problem when k is not bounded, this problem is NP-hard. Recently Iwama, Nishimura, Peterson, Raymond, and Yamashita show that when k is fixed and the field F is fixed, the problem can be solved in polynomial time. One of their key lemmas shows that the number of vertices in the network performing the K encoding operations is at most |F|3kThis paper improves the k bound exponentially to k2|F|2kSince their algorithm's running time depends on this bound exponentially, our bound implies an improved running time.