Almost global problems in the LOCAL model
DOI10.4230/LIPICS.DISC.2018.9zbMATH Open1497.68560OpenAlexW2963789390MaRDI QIDQ5090898FDOQ5090898
Authors: Alkida Balliu, Sebastian F. Brandt, Dennis Olivetti, Jukka Suomela
Publication date: 21 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.DISC.2018.9
Recommendations
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)
Cites Work
- Title not available (Why is that?)
- On the Computational Complexity of Algorithms
- Distributed Computing: A Locality-Sensitive Approach
- Locality in Distributed Graph Algorithms
- The local nature of \(\Delta\)-coloring and its algorithmic applications
- Some simple distributed algorithms for sparse networks
- Deterministic coin tossing with applications to optimal parallel list ranking
- What Can be Computed Locally?
- Title not available (Why is that?)
- Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
- Brief announcement: An exponential separation between randomized and deterministic complexity in the LOCAL model
- Deterministic \((\Delta+1)\)-coloring in sublinear (in \(\Delta\)) time in static, dynamic, and faulty networks
- Distributed degree splitting, edge coloring, and orientations
- A lower bound for the distributed Lovász local lemma
- LCL problems on grids
Cited In (9)
- Local collapses in the Truscott-Brindley model
- Title not available (Why is that?)
- Classification of distributed binary labeling problems
- Message reduction in the LOCAL model is a free lunch
- Local-on-average distributed tasks
- Distributed graph problems through an automata-theoretic lens
- A time hierarchy theorem for the LOCAL model
- LCL problems on grids
- Almost global problems in the LOCAL model
This page was built for publication: Almost global problems in the LOCAL model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090898)