What cannot be computed locally!
From MaRDI portal
Recommendations
- Local computation: lower and upper bounds
- A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
- A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds
- Approximated distributed minimum vertex cover algorithms for bounded degree graphs
- A Local 2-Approximation Algorithm for the Vertex Cover Problem
Cited in
(57)- Empire of colonies: Self-stabilizing and self-organizing distributed algorithm
- What can be verified locally?
- Linear-in- lower bounds in the LOCAL model
- Distributed verification of minimum spanning trees
- Compact distributed certification of planar graphs
- Distributed backup placement
- Local certification of graphs with bounded genus
- A polynomial-time approximation to a minimum dominating set in a graph
- What can be sampled locally?
- Improved deterministic distributed matching via rounding
- A hierarchy of local decision
- Combinatorial algorithms for distributed graph coloring
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Allowing each node to communicate only once in a distributed system: shared whiteboard models
- Proof labeling schemes
- Distributed computing with advice: information sensitivity of graph coloring
- Can we locally compute sparse connected subgraphs?
- Toward more localized local algorithms: removing assumptions concerning global knowledge
- A simple randomized scheme for constructing low-weight \(k\)-connected spanning subgraphs with applications to distributed algorithms
- Membrane computing to enhance time efficiency of minimum dominating set
- Tight bounds for parallel randomized load balancing
- Trading bit, message, and time complexity of distributed algorithms
- Local computation: lower and upper bounds
- An optimal bit complexity randomized distributed MIS algorithm (extended abstract)
- Leveraging Linial’s Locality Limit
- What Can be Computed Locally?
- When Algorithms for Maximal Independent Set and Maximal Matching Run in Sublinear Time
- Distributed graph algorithms and their complexity: an introduction
- Hardness of Distributed Optimization
- What can be computed in a distributed system?
- What can be decided locally without identifiers?
- Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
- What Can be Sampled Locally?
- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
- Efficient distributed approximation algorithms via probabilistic tree embeddings
- Constant-time distributed dominating set approximation
- Making local algorithms wait-free: the case of ring coloring
- Node and edge averaged complexities of local graph problems
- Distributed approximation of capacitated dominating sets
- Local MST computation with short advice
- Exact distributed sampling
- Minimum vertex cover, distributed decision-making, and communication complexity
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Parameterized distributed algorithms
- An optimal bit complexity randomized distributed MIS algorithm
- Distributed algorithms for covering, packing and maximum weighted matching
- Distributed approximation for \(f\)-matching
- A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs
- Approximating bipartite minimum vertex cover in the Congest model
- Sample-and-gather: fast ruling set algorithms in the low-memory MPC model
- The message complexity of distributed graph optimization
- A simple distributed algorithm for sparse fractional covering and packing problems
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Fast deterministic distributed algorithms for sparse spanners
- A simple local 3-approximation algorithm for vertex cover
- An optimal maximal independent set algorithm for bounded-independence graphs
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
This page was built for publication: What cannot be computed locally!
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501510)
