Local MST computation with short advice
From MaRDI portal
Publication:613116
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
Graph theory (including graph drawing) in computer science (68R10) Distributed systems (68M14) Distributed algorithms (68W15)
Related Items (24)
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 ⋮ 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
