Almost global problems in the LOCAL model
type: Item
instance of: scholarly article
title: Almost global problems in the LOCAL model
author: Alkida Balliu
author: Dennis Olivetti
author: Jukka Suomela
author: Sebastian F. Brandt
published in: Distributed Computing
publication date: 2021-09-06T00:00:00Z
full work available at URL: https://arxiv.org/abs/1805.04776
Mathematics Subject Classification ID: 68M14
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 7391413
zbMATH Keywords: distributed complexity theory
zbMATH Keywords: locally checkable labellings
zbMATH Keywords: LOCAL model
MaRDI profile type: Publication
OpenAlex ID: W3017002107
cites work: How much does randomness help with locally checkable problems?
cites work: New classes of distributed time complexity
cites work: Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
cites work: Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
cites work: A lower bound for the distributed Lovász local lemma
cites work: LCL Problems on Grids
cites work: Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
cites work: An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
cites work: A Time Hierarchy Theorem for the LOCAL Model
cites work: Deterministic coin tossing with applications to optimal parallel list ranking
cites work: Distributed Degree Splitting, Edge Coloring, and Orientations
cites work: Q3179347
cites work: On the Computational Complexity of Algorithms
cites work: Q3862379
cites work: Locality in Distributed Graph Algorithms
cites work: What Can be Computed Locally?
cites work: Some simple distributed algorithms for sparse networks
cites work: The local nature of \(\Delta\)-coloring and its algorithmic applications
cites work: Distributed Computing: A Locality-Sensitive Approach
DOI: 10.1007/S00446-020-00375-2
description: scientific article; zbMATH DE number 7391413