LCL problems on grids

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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference article in proceedingsScientificvertaisarvioitu

46 Sitaatiot (Scopus)

Abstrakti

LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Θ(log∗ n), or Θ(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Θ(log∗ n), and Θ(n). However, given an LCL problem it is undecidable whether its complexity is Θ(log∗ n) or Θ(n) in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is Θ(log∗ n), we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal form A′·Sk, where A′ is a finite function, Sk is an algorithm for finding a maximal independent set in kth power of the grid, and k is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.

AlkuperäiskieliEnglanti
OtsikkoPODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing
KustantajaACM
Sivut101-110
Sivumäärä10
VuosikertaPart F129314
ISBN (elektroninen)9781450349925
DOI - pysyväislinkit
TilaJulkaistu - 26 heinäk. 2017
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
TapahtumaACM Symposium on Principles of Distributed Computing - Washington, Yhdysvallat
Kesto: 25 heinäk. 201727 heinäk. 2017
Konferenssinumero: 36

Conference

ConferenceACM Symposium on Principles of Distributed Computing
LyhennettäPODC
Maa/AlueYhdysvallat
KaupunkiWashington
Ajanjakso25/07/201727/07/2017

Sormenjälki

Sukella tutkimusaiheisiin 'LCL problems on grids'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä