Local MST computation with short advice
From MaRDI portal
Publication:613116
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
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, 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