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

DOI10.1007/s00453-009-9361-9zbMath1216.68042MaRDI 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

tree; parallel; advice; broadcasting algorithm; deterministic broadcasting

Mathematics Subject Classification ID

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

68M07: Mathematical problems of computer architecture

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68M14: Distributed systems

Related Items

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

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