  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.
