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. https://resolver.caltech.edu/CaltechAUTHORS:CASisit05
![]()
|
PDF
- Published Version
See Usage Policy. 232kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:CASisit05
Abstract
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: |
| |||||||||
ORCID: |
| |||||||||
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. | |||||||||
Funders: |
| |||||||||
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 | |||||||||
DOI: | 10.1109/ISIT.2005.1523639 | |||||||||
Record Number: | CaltechAUTHORS:CASisit05 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:CASisit05 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 12449 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | Kristin Buxton | |||||||||
Deposited On: | 03 Dec 2008 23:50 | |||||||||
Last Modified: | 08 Nov 2021 22:28 |
Repository Staff Only: item control page