Computer Science – Information Theory
Scientific paper
2009-08-18
Computer Science
Information Theory
8 pages, 3 figures, presented at 47th Allerton Conference on Communication Control and Computing, 2009. Includes more complete
Scientific paper
10.1109/ALLERTON.2009.5394805
The non-uniform demand network coding problem is posed as a single-source and multiple-sink network transmission problem where the sinks may have heterogeneous demands. In contrast with multicast problems, non-uniform demand problems are concerned with the amounts of data received by each sink, rather than the specifics of the received data. In this work, we enumerate non-uniform network demand scenarios under which network coding solutions can be found in polynomial time. This is accomplished by relating the demand problem with the graph coloring problem, and then applying results from the strong perfect graph theorem to identify coloring problems which can be solved in polynomial time. This characterization of efficiently-solvable non-uniform demand problems is an important step in understanding such problems, as it allows us to better understand situations under which the NP-complete problem might be tractable.
Gill John J.
Koo Joseph C.
No associations
LandOfFree
Low-complexity non-uniform demand multicast network coding problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Low-complexity non-uniform demand multicast network coding problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Low-complexity non-uniform demand multicast network coding problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-8101