QQ客服 官方微博 反馈留言

	The Complexity of Network Coding With Two Unit-Rate Multicast Sessions
	Song, Wentu ; Cai, Kai ; Feng, Rongquan ; Yuen, Chau
	2013
关键词	Encoding complexity network coding region decomposition INFORMATION-FLOW ALGORITHMS
英文摘要	The encoding complexity of network coding for single multicast networks has been intensively studied from several aspects: e. g., the time complexity, the required number of encoding links, and the required field size for a linear code solution. However, these issues as well as the solvability are less understood for networks with multiple multicast sessions. Recently, Wang and Shroff showed that the solvability of networks with two unit-rate multicast sessions (2-URMS) can be decided in polynomial time [4]. In this paper, we prove that for the 2-URMS networks: 1) the solvability can be determined with time O(vertical bar E vertical bar); 2) a solution can be constructed with time (vertical bar E vertical bar); 3) an optimal solution can be obtained in polynomial time; 4) the number of encoding links required to achieve a solution is upper-bounded by max {3, 2N-2}; and 5) the field size required to achieve a linear solution is upper-bounded by, max {2, left perpendicular root 2N - 7/4 + 1/2right perpendicular}, where vertical bar E vertical bar is the number of links and is the number of sinks of the underlying network. Both bounds are shown to be tight.; Computer Science, Information Systems; Engineering, Electrical & Electronic; SCI(E); EI; 0; ARTICLE; 9; 5692-5707; 59
语种	英语
出处	SCI ; EI
出版者	ieee transactions on information theory
内容类型	其他
源URL	[http://hdl.handle.net/20.500.11897/157455]
专题	数学科学学院
推荐引用方式 GB/T 7714	Song, Wentu,Cai, Kai,Feng, Rongquan,et al. The Complexity of Network Coding With Two Unit-Rate Multicast Sessions. 2013-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。