DocumentCode
2888497
Title
Bounds and exact values in network encoding complexity with two sinks
Author
Xu, Li ; Han, Guangyue
Author_Institution
Univ. of Hong Kong, Hong Kong, China
fYear
2011
fDate
28-30 Sept. 2011
Firstpage
1462
Lastpage
1469
Abstract
For an acyclic directed network with multiple pairs of sources and sinks and a set of Menger´s paths connecting each pair of source and sink, it is well known that the number of mergings among these Menger´s paths is closely related to network encoding complexity. In this paper, we focus on networks with two distinct sinks and we derive bounds on and exact values of two functions relevant to encoding complexity for such networks.
Keywords
computational complexity; directed graphs; encoding; Menger paths; acyclic directed network; network encoding complexity; Complexity theory; Encoding; Joining processes; Merging; Network coding; Unicast; Upper bound;
fLanguage
English
Publisher
ieee
Conference_Titel
Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on
Conference_Location
Monticello, IL
Print_ISBN
978-1-4577-1817-5
Type
conf
DOI
10.1109/Allerton.2011.6120340
Filename
6120340
Link To Document