Local MST computation with short advice

DOI10.1007/S00224-010-9280-9zbMath1213.68123OpenAlexW2630202923MaRDI QIDQ613116

Emmanuelle Lebhar, Amos Korman, Pierre Fraigniaud

Publication date: 17 December 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-010-9280-9

zbMATH Keywords

minimum spanning treedistributed algorithmlocal computation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (25)

How to use spanning trees to navigate in graphs ⋮ Proof labeling schemes ⋮ Distributed computing with advice: information sensitivity of graph coloring ⋮ How to Use Spanning Trees to Navigate in Graphs ⋮ The ANTS problem ⋮ 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 ⋮ Fast Radio Broadcasting with Advice ⋮ Lower and upper bounds for deterministic convergecast with labeling schemes ⋮ Drawing maps with advice ⋮ Toward more localized local algorithms: removing assumptions concerning global knowledge ⋮ Local Maps: New Insights into Mobile Agent Algorithms ⋮ Tree exploration with advice ⋮ Impact of knowledge on election time in anonymous networks ⋮ Fast radio broadcasting with advice ⋮ Online computation with advice ⋮ Trade-offs between the size of advice and broadcasting time in trees ⋮ Communication algorithms with advice ⋮ Edge exploration of anonymous graph by mobile agent with external help ⋮ Short labeling schemes for topology recognition in wireless tree networks ⋮ Advice complexity of treasure hunt in geometric terrains ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs ⋮ Topology recognition with advice

Cites Work

• Unnamed Item
• Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Proof labeling schemes
• Distributed verification of minimum spanning trees
• Oracle size
• What can be computed locally?
• Distributed Computing – IWDC 2005
• What cannot be computed locally!
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• Automata, Languages and Programming
• Tree Exploration with an Oracle
• Distributed MST for constant diameter graphs

This page was built for publication: Local MST computation with short advice