Survey of local algorithms
From MaRDI portal
Publication:2875112
DOI10.1145/2431211.2431223zbMath1293.68306OpenAlexW2138623498MaRDI QIDQ2875112
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
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)
Related Items (max. 100)
Node labels in local decision ⋮ New techniques and tighter bounds for local computation algorithms ⋮ What can be verified locally? ⋮ Large cuts with local algorithms on triangle-free graphs ⋮ Emptiness problems for distributed automata ⋮ Find Your Place: Simple Distributed Algorithms for Community Detection ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time ⋮ Deterministic local algorithms, unique identifiers, and fractional graph colouring ⋮ About informatics, distributed computing, and our job: a personal view ⋮ Computing large independent sets in a single round ⋮ An asynchronous self-stabilizing approximation for the minimum CDS with safe convergence in UDGs ⋮ Analysing local algorithms in location-aware quasi-unit-disk graphs ⋮ Distributed \(\mathcal{CONGEST}_{B C}\) constant approximation of MDS in bounded genus graphs ⋮ Unnamed Item ⋮ Almost stable matchings by truncating the Gale-Shapley algorithm ⋮ A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs ⋮ A hierarchy of local decision ⋮ Distributed Graph Algorithms and their Complexity: An Introduction ⋮ Improved distributed local approximation algorithm for minimum 2-dominating set in planar graphs ⋮ Constant-time local computation algorithms ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ Unnamed Item ⋮ Best of two local models: centralized local and distributed local algorithms ⋮ Fast and Simple Local Algorithms for 2-Edge Dominating Sets and 3-Total Vertex Covers ⋮ Distributed approximation algorithms for \(k\)-dominating set in graphs of bounded genus and linklessly embeddable graphs ⋮ Weak models of distributed computing, with connections to modal logic ⋮ On the distributed complexity of the semi-matching problem ⋮ Making local algorithms wait-free: the case of ring coloring ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ A topological perspective on distributed network algorithms ⋮ Distributed coloring and the local structure of unit-disk graphs ⋮ A local approximation algorithm for minimum dominating set problem in anonymous planar networks ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Efficient computation of sparse structures ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ How Many Cooks Spoil the Soup? ⋮ How many cooks spoil the soup? ⋮ Unnamed Item ⋮ Proof labeling schemes for reachability-related problems in directed graphs ⋮ Local planar domination revisited ⋮ Oblivious algorithms for the maximum directed cut problem
This page was built for publication: Survey of local algorithms
