Almost global problems in the LOCAL model

DOI10.4230/LIPICS.DISC.2018.9MaRDI QIDQ5090898zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

LOCAL modeldistributed complexity theorylocally checkable labellings

Mathematics Subject Classification ID

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)

Recommendations

• Almost global problems in the LOCAL model
• New classes of distributed time complexity
• A time hierarchy theorem for the LOCAL model
• On the complexity of local distributed graph problems
• LCL problems on grids

Cites work

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 6850477 (Why is no real title available?)
• A lower bound for the distributed Lovász local lemma
• 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
• Deterministic coin tossing with applications to optimal parallel list ranking
• Distributed Computing: A Locality-Sensitive Approach
• Distributed \((\Delta+1)\)-coloring in linear (in \(\Delta\)) time
• Distributed degree splitting, edge coloring, and orientations
• LCL problems on grids
• Locality in Distributed Graph Algorithms
• On the Computational Complexity of Algorithms
• Some simple distributed algorithms for sparse networks
• The local nature of \(\Delta\)-coloring and its algorithmic applications
• What Can be Computed Locally?

Cited in

(9)

• Local collapses in the Truscott-Brindley model
• scientific article; zbMATH DE number 5242355 (Why is no real title available?)
• 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)