Article ID: | iaor20115139 |
Volume: | 60 |
Issue: | 4 |
Start Page Number: | 719 |
End Page Number: | 734 |
Publication Date: | Aug 2011 |
Journal: | Algorithmica |
Authors: | Pelc Andrzej, Fusco G |
Keywords: | communication, networks |
We study the problem of the amount of information required to perform fast broadcasting in tree networks. The source located at the root of a tree has to disseminate a message to all nodes. In each round each informed node can transmit to one child. Nodes do not know the topology of the tree but an oracle knowing it can give a string of bits of