Local Computation

DOI10.1145/2742012zbMath1426.68092arXiv1011.5470OpenAlexW1957963525MaRDI QIDQ3177774

Roger Wattenhofer, Fabian Kuhn, Thomas Moscibroda

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.5470

zbMATH Keywords

lower bounds dominating set locality distributed algorithms maximal matching vertex cover maximal independent set approximation hardness butterfly effect polylog-local

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (46)

Distributed independent sets in interval and segment intersection graphs ⋮ Fast Distributed Approximation for Max-Cut ⋮ Distributed distance domination in graphs with no $K_{2,t}$-minor ⋮ Distributed minimum dominating set approximations in restricted families of graphs ⋮ Constant space and non-constant time in distributed computing ⋮ Distributed reconfiguration of maximal independent sets ⋮ What can be sampled locally? ⋮ Derandomizing local distributed algorithms under bandwidth restrictions ⋮ Node and edge averaged complexities of local graph problems ⋮ Linear-in-$\varDelta $ lower bounds in the LOCAL model ⋮ Deterministic local algorithms, unique identifiers, and fractional graph colouring ⋮ Exact distributed sampling ⋮ Distributed $(\Delta+1)$-Coloring via Ultrafast Graph Shattering ⋮ Distributed dominating sets in interval graphs ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Computing large independent sets in a single round ⋮ Optimal distributed covering algorithms ⋮ The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings ⋮ Distributed MIS in O(log log n) Awake Complexity ⋮ Distributed MIS with Low Energy and Time Complexities ⋮ An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model ⋮ Fooling views: a new lower bound technique for distributed computations under congestion ⋮ (Delta+1) Coloring in the Congested Clique Model ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring ⋮ Combinatorial algorithms for distributed graph coloring ⋮ No sublogarithmic-time approximation scheme for bipartite vertex cover ⋮ Simple and local independent set approximation ⋮ Dynamic networks of finite state machines ⋮ Distributed distance-$r$ covering problems on sparse high-girth graphs ⋮ A topological perspective on distributed network algorithms ⋮ Distributed distance-$r$ covering problems on sparse high-girth graphs ⋮ Distributed Dominating Set Approximations beyond Planar Graphs ⋮ Distributed algorithms for the Lovász local lemma and graph coloring ⋮ Randomized (Delta+1)-Coloring in O(log* Delta) Congested Clique Rounds ⋮ Distributed Approximate Maximum Matching in the CONGEST Model. ⋮ Distributed set cover approximation: Primal-dual with optimal locality ⋮ Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set ⋮ Distributed Reconfiguration of Maximal Independent Sets ⋮ Distributed Spanner Approximation ⋮ Local planar domination revisited ⋮ Distributed Lower Bounds for Ruling Sets ⋮ Linial for lists ⋮ Distributed coloring algorithms for triangle-free graphs ⋮ Constant round distributed domination on graph classes with bounded expansion

This page was built for publication: Local Computation