Local MST computation with short advice

DOI10.1007/s00224-010-9280-9zbMath1213.68123MaRDI QIDQ613116

Pierre Fraigniaud, Amos Korman, Emmanuelle Lebhar

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 tree; distributed algorithm; local computation

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68M14: Distributed systems

68W15: Distributed algorithms

Related Items

Drawing maps with advice, Online computation with advice, Trade-offs between the size of advice and broadcasting time in trees, Tree exploration with advice, Fast radio broadcasting with advice, Communication algorithms with advice, Advice complexity of maximum independent set in sparse and bipartite graphs, How to use spanning trees to navigate in graphs, Proof labeling schemes, Distributed computing with advice: information sensitivity of graph coloring, Toward more localized local algorithms: removing assumptions concerning global knowledge, How to Use Spanning Trees to Navigate in Graphs, Fast Radio Broadcasting with Advice, Local Maps: New Insights into Mobile Agent Algorithms

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