Local MST computation with short advice
From MaRDI portal
Recommendations
- Local computation: lower and upper bounds
- Space-efficient local computation algorithms
- scientific article; zbMATH DE number 4203713
- Local computation algorithms for spanners
- Approximate MST for UDG locally
- Local search: complexity and approximation
- Computing locally injective mappings by advanced MIPS
- Constant-time local computation algorithms
Cites work
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Automata, Languages and Programming
- Distributed Computing – IWDC 2005
- Distributed Computing: A Locality-Sensitive Approach
- Distributed MST for constant diameter graphs
- Distributed verification of minimum spanning trees
- Locality in Distributed Graph Algorithms
- Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
- Oracle size, a new measure of difficulty for communication tasks
- Proof labeling schemes
- Tree Exploration with an Oracle
- Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem
- What can be computed locally?
- What cannot be computed locally!
Cited in
(25)- Computing locally injective mappings by advanced MIPS
- Topology recognition with advice
- Edge exploration of anonymous graph by mobile agent with external help
- Fast rendezvous with advice
- Drawing maps with advice
- 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
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)
