LCL Problems on Grids
LCL Problems on Grids
复制标题
网格拼箱问题
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
P. Uznański
中科院分区：
文献类型：
--
作者：
S. Brandt;J. Hirvonen;Janne H. Korhonen;Tuomo Lempiäinen;P. Östergård;Christopher Purcell;Joel Rybicki;J. Suomela;P. Uznański
LCL或局部可检查标记问题（例如最大独立集，最大匹配和顶点着色）在循环（环形一维网格）中得到了很好的理解：每个问题的复杂度为O（1），Θ（log* n）或Θ（n），并且最优算法的设计可以完全自动化。本文发展了二维环形网格LCL问题的复杂性理论。复杂度类与1维情况相同：O（1），Θ（log* n）和Θ（n）。然而，给定一个LCL问题，它的复杂性是Θ（log* n）还是Θ（n）在二维网格中是不可判定的。然而，如果我们正确地猜测问题的复杂性是Θ（log* n），我们就可以完全自动化最优算法的设计。对于任何问题，我们可以找到一个算法，是一个正常的形式A' o Sk，其中A'是一个有限的功能，Sk是一个算法，找到一个最大的独立集在第k次权力的网格，和k是一个常数。最后，部分自动化设计工具的帮助下，我们分类的复杂性，几个具体的拼箱问题有关的着色和方向。
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.
局部模型中随机复杂性和确定性复杂性之间的指数分离
影响因子：
1.6
作者：
Chang, Yi-Jun;Kopelowitz, Tsvi;Pettie, Seth
通讯作者：
Pettie, Seth
局部模型的时间层次定理
影响因子：
1.6
作者：
Chang, Yi-Jun;Pettie, Seth
通讯作者：
Pettie, Seth