Carregant...

Vés al contingut (premeu Retorn)

# FUTUR. Portal de la Producció Científica dels Investigadors de la UPC

## Minimal contention-free matrices with application to multicasting

Autor
Cohen, J.; Fraigniaud, P.; Mitjana, M.
Tipus d'activitat
Article en revista
Revista
Dimacs series in discrete mathematics and theoretical computer science
Data de publicació
2000-04
Volum
53
Número
-
Pàgina inicial
17
Pàgina final
33
URL
http://hdl.handle.net/2117/804
Resum
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 ro...
Citació
Cohen, Johanne; Fraigniaud, Pierre; Mitjana Riera, Margarida. “Minimal contention-free matrices with application to multicasting”. A: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 1998, vol. 53, núm , p. 17-33.
Grup de recerca
MAPTHE - Anàlisi matricial i Teoria Discreta del Potencial