A Caltech Library Service

Network coding for non-uniform demands

Cassuto, Yuval and Bruck, Jehoshua (2005) Network coding for non-uniform demands. In: International Symposium on Information Theory (ISIT 2005), Adelaide, Australia, 4-9 September 2005. IEEE , Piscataway, NJ, pp. 1720-1724. ISBN 0-7803-9151-9

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


Non-uniform demand networks are defined as a useful connection model, in between multicasts and general connections. In these networks, each sink demands a certain number of messages, without specifying their identities. We study the solvability of such networks and give a tight bound on the number of sinks for which the min cut condition is sufficient. This sufficiency result is unique to the non-uniform demand model and does not apply to general connection networks. We propose constructions to solve networks at, or slightly below capacity, and investigate the effect large alphabets have on the solvability of such networks. We also show that our efficient constructions are suboptimal when used in networks with more sinks, yet this comes with little surprise considering the fact that the general problem is shown to be NP-hard.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2005 IEEE. Reprinted with permission. Publication Date: 4-9 Sept. 2005. This work was supported in part by the Caltech Lee Center for Advanced Networking and by NSF grant ANI-0322475.
Funding AgencyGrant Number
Lee Center for Advanced Networking ,CaltechUNSPECIFIED
National Science FoundationANI-0322475
Subject Keywords:computability; computational complexity; directed graphs; encoding; multicast communication; optimization; NP-hard problem; connection model; min cut condition; network coding; network solvability; nonuniform demand networks
Record Number:CaltechAUTHORS:CASisit05
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:12449
Deposited By: Kristin Buxton
Deposited On:03 Dec 2008 23:50
Last Modified:26 Dec 2012 10:32

Repository Staff Only: item control page