What can be computed locally?

DOI10.1145/167088.167149zbMath1310.68027OpenAlexW1987314757MaRDI QIDQ5248485

Moni Naor, Larry J. Stockmeyer

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/167088.167149

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Related Items (21)

A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Neighborhood graphs and distributed Δ+1-coloring ⋮ Proof labeling schemes ⋮ Distributed computing with advice: information sensitivity of graph coloring ⋮ Local Construction and Coloring of Spanners of Location Aware Unit Disk Graphs ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Impact of locality on location aware unit disk graphs ⋮ On chromatic sums and distributed resource allocation ⋮ Local MST computation with short advice ⋮ The local detection paradigm and its applications to self-stabilization ⋮ Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs ⋮ Improved distributed degree splitting and edge coloring ⋮ Exact distributed sampling ⋮ Brief Announcement: Local Problems in the SUPPORTED Model ⋮ Fast and compact self-stabilizing verification, computation, and fault detection of an MST ⋮ What Can be Computed in a Distributed System? ⋮ Local approximation of the maximum cut in regular graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Distributed distance-\(r\) covering problems on sparse high-girth graphs ⋮ Stabilizing time-adaptive protocols ⋮ Checking Global Graph Properties by Means of Local Computations: the Majority Problem

This page was built for publication: What can be computed locally?