LCL Problems on Grids

DOI10.1145/3087801.3087833zbMath1380.68218arXiv1702.05456OpenAlexW2593376981MaRDI QIDQ5368949

Patric R. J. Östergård, Sebastian F. Brandt, Jukka Suomela, Przemysław Uznański, Janne H. Korhonen, Tuomo Lempiäinen, Christopher Purcell, Juho Hirvonen, Joel Rybicki

Publication date: 11 October 2017

Published in: Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1702.05456

zbMATH Keywords

computational complexitygraph colouringdistributed algorithmslocal modelalgorithm synthesisLCL problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items

Constant space and non-constant time in distributed computing ⋮ Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics ⋮ Locally checkable problems in rooted trees ⋮ Distributed algorithms, the Lovász local lemma, and descriptive combinatorics ⋮ Probabilistic constructions in continuous combinatorics and a bridge to distributed algorithms ⋮ Algorithms and complexity for counting configurations in Steiner triple systems ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Almost global problems in the LOCAL model ⋮ A Time Hierarchy Theorem for the LOCAL Model ⋮ How long it takes for an ordinary node with an ordinary ID to output? ⋮ Distributed Recoloring ⋮ Almost global problems in the LOCAL model ⋮ Local mending ⋮ Distributed algorithms for fractional coloring ⋮ Distributed graph problems through an automata-theoretic Lens

This page was built for publication: LCL Problems on Grids