Scheduling calls for multicasting in tree-networks
Johanne Cohen, Pierre Fraigniaud, Margarida Mitjana Riera · 1999
In this paper, we show that the multicast problem in trees can be expressed in term of arranging rows and columns of boolean matrices. Given a p \\Theta q matrix M with 0-1 entries, the shadow of M is defined as a boolean vector x of q entries such that x i = 0 if and only if there is no 1-entry in the ith column of M , and x i = 1 otherwise. (The shadow x can also be seen as the binary expression of the integer x = P q i=1 x i 2 q\\Gammai . Similarly, every row of M can be seen as the binary expression of an integer.) According to this formalism, the key for solving a multicast problem in trees is shown to be the following. Given a p \\Theta q matrix M with 0-1 entries, finding a matrix M such that: 1. M has at most one 1-entry per column; 2. every row r of M (viewed as the binary expression of an integer) is larger than the corresponding row r of M , 1 r p; and 3. the shadow of M (viewed as an integer) is minimum. We show that there is an O(q(p + q)) algorithm that fin...