# This Collection

By Defense Date By Authors By Titles By Subject

# Statistics

View Statistics All RECERCAT

# My RECERCAT

 Title: Minimal contention-free matrices with application to multicasting Cohen, Johanne; Fraigniaud, Pierre; Mitjana Riera, Margarida Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada I; Universitat Politècnica de Catalunya. COMBGRAF - Combinatòria, Teoria de Grafs i Aplicacions 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 \times q$ matrix $M$ with 0-1 entries, the {\em 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 $i$th column of $M$, and $x_i=1$ otherwise. (The shadow $x$ can also be seen as the binary expression of the integer $x=\sum_{i=1}^{q}x_i 2^{q-i}$. 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 \times 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 \leq r \leq 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 returns $M^*$ for any $p \times q$ boolean matrix $M$. The application of this result is the following: Given a {\em 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. Peer Reviewed Information and Communication Applications, Inc.Operations researchComputer systemsGraph theoryApplication to MulticastingMinimal Contention-free MatricesInvestigació operativaArquitectura de computadorsGrafs, Teoria deClassificació AMS::68 Computer science::68M Computer system organizationClassificació AMS::05 Combinatorics::05C Graph theoryClassificació AMS::90 Operations research, mathematical programming::90B Operations research and management scienceClassificació AMS::94 Information And Communication, Circuits::94A Communication, information Article

# Related documents

## Other documents of the same author

Barrière Figueroa, Eulalia; Cohen, Johanne; Mitjana Riera, Margarida
Barrière Figueroa, Eulalia; Flocchini, Paola; Fomin, Fedor V.; Fraigniaud, Pierre; Nisse, Nicolas; Santoro, Nicola; Thilikos Touloupas, Dimitrios
Barrière Figueroa, Eulalia; Fraigniaud, Pierre; Santoro, Nicola; Thilikos Touloupas, Dimitrios
Comellas Padró, Francesc de Paula; Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel; Mitjana Riera, Margarida
Fiol Mora, Miquel Àngel; Mitjana Riera, Margarida

Coordination

Supporters