Topology recognition with advice

DOI10.1016/J.IC.2016.01.005MaRDI QIDQ259077zbMATH OpenOpenAlexFDO

Authors Emanuele G. Fusco, Andrzej Pelc, Rossella Petreschi

Publication date 10 March 2016

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

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

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)

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.

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

Cites work

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

Cited in

(5)

• Edge exploration of anonymous graph by mobile agent with external help
• 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)