caa a22 4500 445804505 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s00453-009-9361-9 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9361-9 Trade-offs Between the Size of Advice and Broadcasting Time in Trees [Elektronische Daten] [Emanuele Fusco, Andrzej Pelc] 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 advice to the source which can then pass it down the tree with the source message. The quality of a broadcasting algorithm with advice is measured by its competitive ratio: the worst case ratio, taken over n-node trees, between the time of this algorithm and the optimal broadcasting time in the given tree. Our goal is to find a trade-off between the size of advice and the best competitive ratio of a broadcasting algorithm for n-node trees. We establish such a trade-off with an approximation factor of O(n ε), for an arbitrarily small positive constant ε. This is the first communication problem for which a trade-off between the size of advice and the efficiency of the solution is shown for arbitrary size of advice. Springer Science+Business Media, LLC, 2009 Algorithm nationallicence Parallel nationallicence Deterministic broadcasting nationallicence Advice nationallicence Tree nationallicence Fusco Emanuele Computer Science Department, University of Rome "La Sapienza”, 00198, Rome, Italy aut Pelc Andrzej Département d'informatique, Université du Québec en Outaouais, J8X 3X7, Gatineau, Québec, Canada aut Algorithmica Springer-Verlag 60/4(2011-08-01), 719-734 0178-4617 60:4<719 2011 60 453 https://doi.org/10.1007/s00453-009-9361-9 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9361-9 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Fusco Emanuele Computer Science Department, University of Rome "La Sapienza”, 00198, Rome, Italy aut NATIONALLICENCE 700 1- Pelc Andrzej Département d'informatique, Université du Québec en Outaouais, J8X 3X7, Gatineau, Québec, Canada aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/4(2011-08-01), 719-734 0178-4617 60:4<719 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer