๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An Optimal Algorithm for Broadcasting Multiple Messages in Trees

โœ Scribed by Krzysztof Diks; Andrzej Lingas; Andrzej Pelc

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
118 KB
Volume
59
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

We consider multiple message broadcasting in tree networks. The source (considered as the root of the tree) has k messages which have to be broadcast to all nodes of the tree. In every time unit each node can send one of its already obtained messages to one of its children. A k-message broadcasting scheme prescribes in which time unit a given node should send a message to which child. It is k-optimal if it achieves the smallest possible time for broadcasting k messages from the source to all nodes. We give an algorithm to construct a k-optimal broadcasting scheme for an arbitrary n-node tree. The time complexity of our algorithm is O(nk), i.e., the best possible.

๐Ÿ“œ SIMILAR VOLUMES

H. Almuallim, An efficient algorithm for
H. Almuallim, An efficient algorithm for optimal of decision trees
๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 69 KB

Situations in which them is competition among possible contractor agents or possible manager agents are also considered. In all situations we assume that the contractor can choose a level of effort when carrying out the task and we would like the contractor to carry out the task efficiently without

A linear-time algorithm for broadcast do
A linear-time algorithm for broadcast domination in a tree
โœ John Dabney; Brian C. Dean; Stephen T. Hedetniemi ๐Ÿ“‚ Article ๐Ÿ“… 2009 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 268 KB

## Abstract The broadcast domination problem is a variant of the classical minimum dominating set problem in which a transmitter of power __p__ at vertex __v__ is capable of dominating (broadcasting to) all vertices within distance __p__ from __v__. Our goal is to assign a broadcast power __f__(__v

A New Efficient Algorithm for Embedding
A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube
โœ Volker Heun; Ernst W. Mayr ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 250 KB

The d-dimensional binary hypercube is a very popular model of parallel computation. On the other hand, the execution of many algorithms can be represented by binary trees, making it desirable to simulate binary trees on a hypercube. In this paper, we present a simple one-to-one embedding of arbitrar