What Can be Computed Locally?
From MaRDI portal
Publication:4862796
DOI10.1137/S0097539793254571zbMath0845.68006OpenAlexW2017345786WikidataQ56041881 ScholiaQ56041881MaRDI QIDQ4862796
Moni Naor, Larry J. Stockmeyer
Publication date: 15 September 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793254571
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
A silent self-stabilizing algorithm for the generalized minimal \(k\)-dominating set problem, Node labels in local decision, New techniques and tighter bounds for local computation algorithms, Ramanujan graphings and correlation decay in local algorithms, Exact Bounds for Distributed Graph Colouring, Planarity can be verified by an approximate proof labeling scheme in constant-time, Can we locally compute sparse connected subgraphs?, An iterative domain decomposition, spectral finite element method on non-conforming meshes suitable for high frequency Helmholtz problems, What can be verified locally?, Constant space and non-constant time in distributed computing, Distributed approximation of capacitated dominating sets, Network Decomposition and Distributed Derandomization (Invited Paper), What can be sampled locally?, Derandomizing local distributed algorithms under bandwidth restrictions, Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics, Linear-in-\(\varDelta \) lower bounds in the LOCAL model, Locally checkable problems in rooted trees, Synchronous counting and computational algorithm design, Distributed algorithms, the Lovász local lemma, and descriptive combinatorics, Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time, Deterministic local algorithms, unique identifiers, and fractional graph colouring, Component stability in low-space massively parallel computation, Lower bound for constant-size local certification, Unnamed Item, Distributed half-integral matching and beyond, Distributed graph problems through an automata-theoretic lens, Computing large independent sets in a single round, Distributed verification of minimum spanning trees, Analysing local algorithms in location-aware quasi-unit-disk graphs, Unnamed Item, Constructing near spanning trees with few local inspections, Locality and checkability in wait-free computing, Toward more localized local algorithms: removing assumptions concerning global knowledge, Almost stable matchings by truncating the Gale-Shapley algorithm, An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, A hierarchy of local decision, Fooling views: a new lower bound technique for distributed computations under congestion, Local Maps: New Insights into Mobile Agent Algorithms, Leveraging Linial’s Locality Limit, A Limit to the Power of Multiple Nucleation in Self-assembly, Hundreds of impossibility results for distributed computing, An optimal bit complexity randomized distributed MIS algorithm, Distributed algorithms for covering, packing and maximum weighted matching, Further optimizations of CSIDH: a systematic approach to efficient strategies, permutations, and bound vectors, (Delta+1) Coloring in the Congested Clique Model, Almost global problems in the LOCAL model, Constant-time local computation algorithms, Deciding and verifying network properties locally with few output bits, A Time Hierarchy Theorem for the LOCAL Model, On mobile agent verifiable problems, Representing graphs implicitly using almost optimal space, Local approximability of max-min and min-max linear programs, Randomized distributed decision, No sublogarithmic-time approximation scheme for bipartite vertex cover, A simple local 3-approximation algorithm for vertex cover, Unnamed Item, How long it takes for an ordinary node with an ordinary ID to output?, Weak models of distributed computing, with connections to modal logic, Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes, Making local algorithms wait-free: the case of ring coloring, Local edge colouring of Yao-like subgraphs of unit disk graphs, Unnamed Item, Local algorithms for sparse spanning graphs, A local approximation algorithm for minimum dominating set problem in anonymous planar networks, The Impact of Locality in the Broadcast Congested Clique Model, Equilibria of Games in Networks for Local Tasks, Derandomizing Distributed Algorithms with Small Messages: Spanners and Dominating Set, Locality and Checkability in Wait-Free Computing, An Optimal Bit Complexity Randomized Distributed MIS Algorithm (Extended Abstract), Almost global problems in the LOCAL model, Local mending, Distributed interactive proofs for the recognition of some geometric intersection graph classes, Unnamed Item, Distributed Lower Bounds for Ruling Sets, Local certification of graphs with bounded genus, Introduction to local certification, Allowing each node to communicate only once in a distributed system: shared whiteboard models, Distributed graph problems through an automata-theoretic Lens
