Degraded two-message multicast over graphs
In this work we consider a graph G where a common source sends two messages W1 and W2 to several receivers D1, D2, . . . , DK. The first two receivers D1 and D2 would like to receive message W1, while receivers D3, . . . , DK would like to receive both messages W1,W2. We provide an outer bound on the rate region for arbitrary K, that depends on graph properties. We prove that this bound is achievable for K = 3 using carefully selected linear operations at the network nodes. The achievability proof is build on our result in  and is illustrating the potential connections of communication over deterministic channels and communication over graphs.
Record created on 2011-02-21, modified on 2016-08-09