Title :
A graph theoretical approach to network encoding complexity
Author :
Xu, E.L. ; Weiping Shang ; Guangyue Han
Author_Institution :
Univ. of Hong Kong, Hong Kong, China
Abstract :
For an acyclic directed network with multiple pairs of sources and sinks and a group of edge-disjoint paths connecting each pair of source and sink, it is known that the number of mergings among different groups of edge-disjoint paths is closely related to network encoding complexity. Using this connection, we derive exact values of and bounds on two functions relevant to encoding complexity for such networks.
Keywords :
directed graphs; network coding; source coding; acyclic directed network; edge-disjoint path; graph theoretical approach; network encoding complexity; sink pair; source pair; Complexity theory; Encoding; Merging; Network coding; Receivers; Unicast; Upper bound;
Conference_Titel :
Information Theory and its Applications (ISITA), 2012 International Symposium on
Conference_Location :
Honolulu, HI
Print_ISBN :
978-1-4673-2521-9