论文标题
关于本地可检查问题的新方法
A new approach on locally checkable problems
论文作者
论文摘要
通过提供一个新的框架，我们在有限的树宽图中扩展了有关本地可检查问题的先前结果。结果，我们在多项式时间内显示了如何解决有限的树宽图，双罗马统治和Grundy统治，以及其他以前没有这种算法的问题。此外，通过证明有界程度和有界树宽图的固定功率也是有界程度和有界的树宽图，我们可以扩大可以在多项式时间内解决这些图形类别的问题家族，包括距离着色问题和距离上色问题和距离主导问题（对于边界距离）。
By providing a new framework, we extend previous results on locally checkable problems in bounded treewidth graphs. As a consequence, we show how to solve, in polynomial time for bounded treewidth graphs, double Roman domination and Grundy domination, among other problems for which no such algorithm was previously known. Moreover, by proving that fixed powers of bounded degree and bounded treewidth graphs are also bounded degree and bounded treewidth graphs, we can enlarge the family of problems that can be solved in polynomial time for these graph classes, including distance coloring problems and distance domination problems (for bounded distances).
