Minimal contention-free matrices with application to multicasting
Johanne Cohen, Pierre Fraigniaud, Margarida Mitjana Riera · DIMACS series in discrete mathematics and theoretical computer science · 2000
In this paper, we s h o w that the multicast problem in trees can be expressed in term of arranging rows and columns of boolean matrices.Given a p q matrix M with 0-1 entries, the shadow of M is dened as a boolean vector x of q entries such t h a t 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;i .Similarly, e v ery 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 q matrix M with 0-1 entries, nding 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 o f M (viewed as an integer) is minimum.We show that there is an O(q(p + q)) algorithm that returns M for any p q boolean matrix M. The application of this result is the following: Given a directed tree T whose arcs are oriented from the root toward the leaves, and a subset of nodes D, there exists a polynomial-time algorithm that computes an optimal multicast protocol from the root to all nodes of D in the all-port line model.