Almost global problems in the LOCAL model

DOI10.4230/LIPIcs.DISC.2018.9zbMath1497.68560OpenAlexW2963789390MaRDI QIDQ5090898

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

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.DISC.2018.9

zbMATH Keywords

LOCAL modeldistributed complexity theorylocally checkable labellings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (3)

Locally checkable problems in rooted trees ⋮ Distributed graph problems through an automata-theoretic lens ⋮ A Time Hierarchy Theorem for the LOCAL Model

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
• What Can be Computed Locally?
• Some simple distributed algorithms for sparse networks
• On the Computational Complexity of Algorithms
• A lower bound for the distributed Lovász local lemma
• Brief Announcement
• LCL Problems on Grids
• Distributed $(\Delta+1)$-Coloring in Linear (in $\Delta$) Time

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