An improved bound for multiple source-sink linear network coding

摘要

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|^3k This paper improves the k bound exponentially to k² |F|^2k Since their algorithm''s running time depends on this bound exponentially, our bound implies an improved running time.