To access the full text documents, please follow this link: http://hdl.handle.net/2117/804

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 research
Computer systems
Graph theory
Application to Multicasting
Minimal Contention-free Matrices
Investigació operativa
Arquitectura de computadors
Grafs, Teoria de
Classificació AMS::68 Computer science::68M Computer system organization
Classificació AMS::05 Combinatorics::05C Graph theory
Classificació AMS::90 Operations research, mathematical programming::90B Operations research and management science
Classificació AMS::94 Information And Communication, Circuits::94A Communication, information
Article
         

Show full item record

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