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

• 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

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)

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)