Trade-offs between the size of advice and broadcasting time in trees

DOI10.1007/s00453-009-9361-9zbMath1216.68042OpenAlexW2072269078MaRDI QIDQ547287

Emanuele G. Fusco, Andrzej Pelc

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.401.5029

zbMATH Keywords

treeparalleladvicebroadcasting algorithmdeterministic broadcasting

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Mathematical problems of computer architecture (68M07) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Related Items (10)

Finding the size and the diameter of a radio network using short labels ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Fast rendezvous with advice ⋮ Drawing maps with advice ⋮ Impact of knowledge on election time in anonymous networks ⋮ Online computation with advice ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Topology recognition with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local MST computation with short advice
• Optimal graph exploration without good maps
• Broadcasting in geometric radio networks
• A lower bound for radio broadcast
• The impact of information on broadcasting time in linear radio networks.
• The power of a pebble: Exploring and mapping directed graphs
• Optimal deterministic broadcasting in known topology radio networks
• Activating anonymous ad hoc radio networks
• A trade-off between information and communication in broadcast protocols
• Fast Radio Broadcasting with Advice
• Approximate distance oracles
• Information Dissemination in Trees
• Approximation Algorithms for Minimum-Time Broadcast
• Proof labeling schemes
• Oracle size
• Graph Searching with Advice
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring
• Broadcasting algorithms in radio networks with unknown topology
• Automata, Languages and Programming
• Tree Exploration with an Oracle
• Broadcasting in undirected ad hoc radio networks

This page was built for publication: Trade-offs between the size of advice and broadcasting time in trees