Survey of local algorithms
From MaRDI portal
Publication:2875112
DOI10.1145/2431211.2431223zbMATH Open1293.68306OpenAlexW2138623498MaRDI QIDQ2875112FDOQ2875112
Authors: Jukka Suomela 
Publication date: 13 August 2014
Published in: ACM Computing Surveys (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10138/40800
Recommendations
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)
Cited In (52)
- A topological perspective on distributed network algorithms
- Local algorithms for graphs
- A hierarchy of local decision
- Weak models of distributed computing, with connections to modal logic
- Making local algorithms wait-free: the case of ring coloring
- Derandomizing local distributed algorithms under bandwidth restrictions
- Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs
- Fast and simple local algorithms for 2-edge dominating sets and 3-total vertex covers
- Efficient algorithms for local ranking
- Distributed coloring and the local structure of unit-disk graphs
- On the distributed complexity of the semi-matching problem
- No sublogarithmic-time approximation scheme for bipartite vertex cover
- Local-Global Phenomena in Graphs
- Distributed domination on sparse graph classes
- New techniques and tighter bounds for local computation algorithms
- Best of two local models: centralized local and distributed local algorithms
- A local approximation algorithm for minimum dominating set problem in anonymous planar networks
- About informatics, distributed computing, and our job: a personal view
- Almost stable matchings by truncating the Gale-Shapley algorithm
- Deterministic local algorithms, unique identifiers, and fractional graph colouring
- Title not available (Why is that?)
- Distributed set cover approximation: primal-dual with optimal locality
- Emptiness problems for distributed automata
- Distributed coloring and the local structure of unit-disk graphs
- An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs
- Find Your Place: Simple Distributed Algorithms for Community Detection
- What can be verified locally?
- A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs
- Title not available (Why is that?)
- Distributed Dominating Set Approximations beyond Planar Graphs
- Oblivious algorithms for the maximum directed cut problem
- The topology of local computing in networks
- Title not available (Why is that?)
- Infinite networks, halting and local algorithms
- Efficient computation of sparse structures
- Distributed graph algorithms and their complexity: an introduction
- Constant-time local computation algorithms
- Analysing local algorithms in location-aware quasi-unit-disk graphs
- Distributed computing in the asynchronous LOCAL model
- Emptiness problems for distributed automata
- How many cooks spoil the soup?
- Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs
- Large cuts with local algorithms on triangle-free graphs
- A time hierarchy theorem for the LOCAL model
- Computing large independent sets in a single round
- Distributed Computing: A Locality-Sensitive Approach
- Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs
- Delay and cooperation in nonstochastic bandits
- Local planar domination revisited
- Proof labeling schemes for reachability-related problems in directed graphs
- How Many Cooks Spoil the Soup?
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
This page was built for publication: Survey of local algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875112)
