Communication algorithms with advice

DOI10.1016/J.JCSS.2009.07.002MaRDI QIDQ972382zbMATHOpenAlexFDO

Authors Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc

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

graphnetworkalgorithmbroadcastingmessage complexitysize of advicewakeup

Mathematics Subject Classification ID

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

Recommendations

• Oracle size, a new measure of difficulty for communication tasks
• Fast Radio Broadcasting with Advice
• Fast radio broadcasting with advice
• Trade-offs between the size of advice and broadcasting time in trees
• Deterministic communication in radio networks

Cites work

• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 52113 (Why is no real title available?)
• scientific article; zbMATH DE number 2119757 (Why is no real title available?)
• A trade-off between information and communication in broadcast protocols
• Approximate distance oracles
• Broadcasting algorithms in radio networks with unknown topology
• Broadcasting in UDG radio networks with unknown topology
• Compact labeling schemes for ancestor queries. (Extended abstract)
• Distance labeling in graphs (extended abstract)
• Distributed Computing – IWDC 2005
• Distributed computing with advice: information sensitivity of graph coloring
• Fast Radio Broadcasting with Advice
• Faster communication in known topology radio networks
• Graph Searching with Advice
• Hundreds of impossibility results for distributed computing
• Local MST computation with short advice
• On the effect of the deployment setting on broadcasting in Euclidean radio networks
• Optimal deterministic broadcasting in known topology radio networks
• Optimal graph exploration without good maps
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Proof labeling schemes
• Selective families, superimposed codes, and broadcasting on unknown radio networks. (Extended abstract)
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• The power of a pebble: Exploring and mapping directed graphs
• Tree exploration with advice
• Universal codeword sets and representations of the integers

Cited in

(19)

• Trade-offs between the size of advice and broadcasting time in trees
• Deterministic size discovery and topology recognition in radio networks with short labels
• Treasure hunt with advice
• Finding the size and the diameter of a radio network using short labels
• Four shades of deterministic leader election in anonymous networks
• Advice complexity of treasure hunt in geometric terrains
• Distributed graph searching with a sense of direction
• Advice complexity of maximum independent set in sparse and bipartite graphs
• Edge exploration of anonymous graph by mobile agent with external help
• Oracle size, a new measure of difficulty for communication tasks
• Locality and checkability in wait-free computing
• Fast rendezvous with advice
• Locality and checkability in wait-free computing
• Topology recognition with advice
• Treasure hunt in graph using pebbles
• Toward more localized local algorithms: removing assumptions concerning global knowledge
• Fast Radio Broadcasting with Advice
• Impact of knowledge on election time in anonymous networks
• Fast radio broadcasting with advice

This page was built for publication: Communication algorithms with advice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972382)