The following pages link to What cannot be computed locally! (Q5501510):
Displaying 47 items.
- Tight bounds for parallel randomized load balancing (Q287991) (← links)
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring (Q518926) (← links)
- Distributed approximation of capacitated dominating sets (Q613113) (← links)
- Local MST computation with short advice (Q613116) (← links)
- Analysing local algorithms in location-aware quasi-unit-disk graphs (Q642985) (← links)
- An optimal bit complexity randomized distributed MIS algorithm (Q658666) (← links)
- Distributed algorithms for covering, packing and maximum weighted matching (Q661048) (← links)
- A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs (Q666086) (← links)
- Deterministic local algorithms, unique identifiers, and fractional graph colouring (Q896700) (← links)
- Fast deterministic distributed algorithms for sparse spanners (Q930906) (← links)
- A simple local 3-approximation algorithm for vertex cover (Q987844) (← links)
- An optimal maximal independent set algorithm for bounded-independence graphs (Q992507) (← links)
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition (Q992509) (← links)
- Empire of colonies: Self-stabilizing and self-organizing distributed algorithm (Q1004316) (← links)
- What can be verified locally? (Q1672006) (← links)
- Linear-in-\(\varDelta \) lower bounds in the LOCAL model (Q1689747) (← links)
- Distributed verification of minimum spanning trees (Q1954247) (← links)
- Compact distributed certification of planar graphs (Q2037111) (← links)
- Distributed backup placement (Q2084982) (← links)
- Local certification of graphs with bounded genus (Q2104916) (← links)
- A polynomial-time approximation to a minimum dominating set in a graph (Q2166772) (← links)
- What can be sampled locally? (Q2189170) (← links)
- Improved deterministic distributed matching via rounding (Q2189173) (← links)
- A hierarchy of local decision (Q2219059) (← links)
- Combinatorial algorithms for distributed graph coloring (Q2251151) (← links)
- No sublogarithmic-time approximation scheme for bipartite vertex cover (Q2256970) (← links)
- Dynamic networks of finite state machines (Q2292917) (← links)
- Allowing each node to communicate only once in a distributed system: shared whiteboard models (Q2355326) (← links)
- Proof labeling schemes (Q2377139) (← links)
- Distributed computing with advice: information sensitivity of graph coloring (Q2377267) (← links)
- Can we locally compute sparse connected subgraphs? (Q2399362) (← links)
- Beeping a maximal independent set (Q2441534) (← links)
- Toward more localized local algorithms: removing assumptions concerning global knowledge (Q2441787) (← links)
- A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms (Q2456363) (← links)
- Membrane computing to enhance time efficiency of minimum dominating set (Q2630783) (← links)
- Trading Bit, Message, and Time Complexity of Distributed Algorithms (Q3095315) (← links)
- An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract) (Q3408183) (← links)
- Leveraging Linial’s Locality Limit (Q3540245) (← links)
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time (Q5091165) (← links)
- Distributed Graph Algorithms and their Complexity: An Introduction (Q5135263) (← links)
- What Can be Computed in a Distributed System? (Q5170751) (← links)
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes (Q5458525) (← links)
- Efficient distributed approximation algorithms via probabilistic tree embeddings (Q5917892) (← links)
- Constant-time distributed dominating set approximation (Q5917933) (← links)
- Making local algorithms wait-free: the case of ring coloring (Q5920224) (← links)
- Node and edge averaged complexities of local graph problems (Q6071120) (← links)
- Time-optimal construction of overlay networks (Q6096036) (← links)
