Solving the Two Simple Multicast Network Coding Problem in Time O(E)

摘要：

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.

关键词： network coding information flow region decompositio

作者: Wentu Song Kai Cai Rongquan Feng Wang Rui

作者单位: LMAM, School of Mathematical Sciences Peking University Beijing, China Institute of Computing Technology Chinese Academy of Sciences Beijing, China LMAM, School of Mathematical Sciences Peking University,Beijing, China

会议类型: 国际会议

会议名称: 2011 International Conference on Information and Computer Networks(ICICN 2011)(2011年信息与计算机网络国际会议)

会议地点: 贵阳

会议语种:英文

页码: 427-431

在线出版日期: 2011-01-26（万方平台首次上网日期，不代表论文的发表时间）