Topology recognition with advice

DOI10.1016/J.IC.2016.01.005zbMATH Open1336.68198arXiv1601.06040OpenAlexW2251394987MaRDI QIDQ259077FDOQ259077

Emanuele G. Fusco, Rossella Petreschi, Andrzej Pelc

Publication date: 10 March 2016

Published in: Information and Computation (Search for Journal in Brave)

Abstract: In topology recognition, each node of an anonymous network has to deterministically produce an isomorphic copy of the underlying graph, with all ports correctly marked. This task is usually unfeasible without any a priori information. Such information can be provided to nodes as advice. An oracle knowing the network can give a (possibly different) string of bits to each node, and all nodes must reconstruct the network using this advice, after a given number of rounds of communication. During each round each node can exchange arbitrary messages with all its neighbors and perform arbitrary local computations. The time of completing topology recognition is the number of rounds it takes, and the size of advice is the maximum length of a string given to nodes. We investigate tradeoffs between the time in which topology recognition is accomplished and the minimum size of advice that has to be given to nodes. We provide upper and lower bounds on the minimum size of advice that is sufficient to perform topology recognition in a given time, in the class of all graphs of size $n$ and diameter $Dlealphan$, for any constant $alpha<1$. In most cases, our bounds are asymptotically tight.

Full work available at URL: https://arxiv.org/abs/1601.06040

Recommendations

• Drawing maps with advice
• Drawing maps with advice
• Topology recognition and leader election in colored networks
• Deterministic Graph Exploration with Advice
• Deterministic graph exploration with advice

zbMATH Keywords

networkadvicetopology recognitiontradeoff

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Network design and communication in computer systems (68M10)

Cites Work

• Distance labeling in graphs
• Graph searching with advice
• Computing Boolean functions on anonymous networks
• Proof labeling schemes
• Distributed computing with advice: information sensitivity of graph coloring
• Compact labeling schemes for ancestor queries. (Extended abstract)
• Computing anonymously with arbitrary knowledge
• Anonymous networks
• Renaming in an asynchronous environment
• Approximate distance oracles
• Computing on an anonymous ring
• Decentralized extrema-finding in circular configurations of processors
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• Drawing maps with advice
• Distributed Computing: A Locality-Sensitive Approach
• Labeling Schemes for Flow and Connectivity
• Label-guided graph exploration by a finite automaton
• Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs
• Online computation with advice
• Trade-offs between the size of advice and broadcasting time in trees
• Local MST computation with short advice
• How much memory is needed for leader election
• Tree exploration with advice
• Fast radio broadcasting with advice
• Communication algorithms with advice

Cited In (6)

• Edge exploration of anonymous graph by mobile agent with external help
• Short labeling schemes for topology recognition in wireless tree networks
• Impact of knowledge on election time in anonymous networks
• Deterministic size discovery and topology recognition in radio networks with short labels
• Four shades of deterministic leader election in anonymous networks
• Finding the size and the diameter of a radio network using short labels

This page was built for publication: Topology recognition with advice

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