Summary: Computation of Broadcasting Multiple Messages in a Positive
A. Averbuch Y. Roditty B. Shoham
Department of Computer Science
School of Mathematical Sciences
Tel Aviv University
Ramat Aviv, Tel Aviv 69978
In this paper we present algorithms for locating the vertices in a tree of n vertices of pos
itive edgeweighted tree and a positive vertexweighted tree from which we broadcast multiple
messages in a minimum cost. Their complexity is O(n 2 log n). It improves a direct recursive
approach which gives O(n 3 ). In case where all the weights are equal to one the complexity is
Efficient broadcasting is a key component in achieving high performance (throughput) from parallel
and distributed processing.
The motivation for this work was triggered by our interest in investigating the problem how to
perform optimal query on distributed database on diverse MIMD multiprocessor architectures .