Local MST computation with short advice
From MaRDI portal
Publication:613116
DOI10.1007/S00224-010-9280-9zbMATH Open1213.68123OpenAlexW2630202923MaRDI QIDQ613116FDOQ613116
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 algorithms (68W15) Distributed systems (68M14)
Cites Work
- Title not available (Why is that?)
- Distributed Computing: A Locality-Sensitive Approach
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Locality in Distributed Graph Algorithms
- What cannot be computed locally!
- Distributed MST for constant diameter graphs
- Oracle size
- Automata, Languages and Programming
- What can be computed locally?
- Proof labeling schemes
- Distributed verification of minimum spanning trees
- Tree Exploration with an Oracle
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- Distributed Computing – IWDC 2005
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
Cited In (26)
- Edge exploration of anonymous graph by mobile agent with external help
- Topology recognition with advice
- Fast rendezvous with advice
- Drawing maps with advice
- Short labeling schemes for topology recognition in wireless tree networks
- Online computation with advice
- Trade-offs between the size of advice and broadcasting time in trees
- Impact of knowledge on election time in anonymous networks
- Tree exploration with advice
- Fast radio broadcasting with advice
- Communication algorithms with advice
- Deterministic size discovery and topology recognition in radio networks with short labels
- How to Use Spanning Trees to Navigate in Graphs
- Four shades of deterministic leader election in anonymous networks
- How to use spanning trees to navigate in graphs
- Distributed computing with advice: information sensitivity of graph coloring
- Proof labeling schemes
- Finding the size and the diameter of a radio network using short labels
- Local Maps: New Insights into Mobile Agent Algorithms
- Advice complexity of treasure hunt in geometric terrains
- Fast Radio Broadcasting with Advice
- The ANTS problem
- Lower and upper bounds for deterministic convergecast with labeling schemes
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- Advice complexity of maximum independent set in sparse and bipartite graphs
- Computing locally injective mappings by advanced MIPS
Recommendations
- Local Computation 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Approximate MST for UDG locally 👍 👎
- Local search: complexity and approximation 👍 👎
- Computing locally injective mappings by advanced MIPS 👍 👎
- Constant-time local computation algorithms 👍 👎
This page was built for publication: Local MST computation with short advice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q613116)
