The encoding complexity for network coding with one multicast sessions has been intensively studied but less understood for multiple sessions. We investigate the encoding complexity for 2 simple multicast sessions by using a region decomposition method and prove that: (1) A network coding solution can be obtained with time O(|E|); (2) Max{3, 2N-2} encoding links is sufficient to achieve a solution; and (3) A finite field of size max{2, √(2N-7/4) } is sufficient to achieve a solution, where |E| is the number of links and N is the number of sinks.
Kai Cai received his Ph.D. in mathematics from Peking University in 2004. He continued as a postdoctoral researcher at Tsinghua University from 2004 to 2006. He visited the Hong Kong University of Science and Technology from 2006 to 2007. After that, he joined the Institute of Computing Technology, Chinese Academy of Sciences. His research interest lies in Network coding, Sequences Design, Combinatorics, etc.
