Communication algorithms with advice

DOI10.1016/j.jcss.2009.07.002zbMath1201.68017OpenAlexW1971694274MaRDI QIDQ972382

Andrzej Pelc, David Ilcinkas, Pierre Fraigniaud

Publication date: 25 May 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2009.07.002

zbMATH Keywords

networkalgorithmgraphbroadcastingmessage complexitysize of advicewakeup

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10)

Related Items (15)

Treasure Hunt with Advice ⋮ Finding the size and the diameter of a radio network using short labels ⋮ Deterministic size discovery and topology recognition in radio networks with short labels ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Fast rendezvous with advice ⋮ Treasure hunt in graph using pebbles ⋮ Locality and checkability in wait-free computing ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Impact of knowledge on election time in anonymous networks ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Locality and Checkability in Wait-Free Computing ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Distributed graph searching with a sense of direction ⋮ Topology recognition with advice

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local MST computation with short advice
• Optimal graph exploration without good maps
• Tree exploration with advice
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• The power of a pebble: Exploring and mapping directed graphs
• Optimal deterministic broadcasting in known topology radio networks
• Broadcasting in UDG radio networks with unknown topology
• Distributed computing with advice: information sensitivity of graph coloring
• A trade-off between information and communication in broadcast protocols
• Fast Radio Broadcasting with Advice
• Approximate distance oracles
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• Universal codeword sets and representations of the integers
• Hundreds of impossibility results for distributed computing
• Proof labeling schemes
• Faster communication in known topology radio networks
• Graph Searching with Advice
• Broadcasting algorithms in radio networks with unknown topology
• Distributed Computing – IWDC 2005
• On the effect of the deployment setting on broadcasting in Euclidean radio networks

This page was built for publication: Communication algorithms with advice