Name
Abstract | ||
|---|---|---|
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' o 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3087801.3087833 | PODC |
Keywords | DocType | Volume |
distributed algorithms, LOCAL model, LCL problems, computational complexity, algorithm synthesis, graph colouring | Conference | abs/1702.05456 |
Citations | PageRank | References |
4 | 0.41 | 29 |
Authors | ||
9 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sebastian C. Brandt | 1 | 274 | 27.02 |
| Juho Hirvonen | 2 | 106 | 11.81 |
| Janne Korhonen | 3 | 71 | 10.52 |
| Tuomo Lempiäinen | 4 | 55 | 4.35 |
| Patric R. J. Östergård | 5 | 609 | 70.61 |
| Christopher Purcell | 6 | 9 | 1.25 |
| Joel Rybicki | 7 | 78 | 9.69 |
| Jukka Suomela | 8 | 600 | 46.99 |
| Przemysław Uznański | 9 | 51 | 17.11 |