Almost global problems in the LOCAL model
From MaRDI portal
Publication:5090898
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
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