Solving the two simple multicast network coding problem in time O(|E|)
Wentu Song, Kai Cai, Rongquan Feng, Rui Wang · 2011
The multiple multicast network coding problem is a challenging topic and have attracted significant attentions from the network coding community. The recent work of Wang and Shroff characterized the solvability of two simple multicast network coding problem by paths with controlled edge-overlap conditions, and showed its solvability can be determined in polynomial time. However, according to their method it is still of extraordinary complexity to obtain a network coding solution. In this paper, we propose an O(|E|)-time algorithm to determine the solvability of such networks. Based on our method, a network coding solution of such networks can also be obtained in time O(|E|), where E is the link set of the network. Moreover, we prove that a field of size q≥|E| is sufficient to achieve the network coding solution.