Almost global problems in the LOCAL model

DOI10.1007/S00446-020-00375-2OpenAlexW3017002107MaRDI QIDQ1981631

Alkida Balliu, Jukka Suomela, Dennis Olivetti, Sebastian F. Brandt

Publication date: 6 September 2021

Published in: Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

LOCAL modeldistributed complexity theorylocally checkable labellings

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Related Items (1)

Distributed graph problems through an automata-theoretic Lens

Cites Work

• Unnamed Item
• Unnamed Item
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks
• Deterministic coin tossing with applications to optimal parallel list ranking
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Degree Splitting, Edge Coloring, and Orientations
• An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model
• A Time Hierarchy Theorem for the LOCAL Model
• What Can be Computed Locally?
• Distributed Edge Coloring and a Special Case of the Constructive Lovász Local Lemma
• Some simple distributed algorithms for sparse networks
• New classes of distributed time complexity
• On the Computational Complexity of Algorithms
• A lower bound for the distributed Lovász local lemma
• LCL Problems on Grids
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time
• How much does randomness help with locally checkable problems?

This page was built for publication: Almost global problems in the LOCAL model