INVESTIGADORES
BONOMO flavia
artículos
Título:
A new approach on locally checkable problems
Autor/es:
BONOMO-BRABERMAN, FLAVIA; GONZALEZ, CAROLINA LUC√ćA
Revista:
DISCRETE APPLIED MATHEMATICS
Editorial:
ELSEVIER SCIENCE BV
Referencias:
Lugar: Amsterdam; Año: 2022 vol. 314 p. 53 - 80
ISSN:
0166-218X
Resumen:
By providing a new framework, we extend previous results on locally checkable problems in boundedtreewidth graphs. As a consequence, we show how to solve, in polynomial time for bounded treewidthgraphs, [k]-Roman domination and Grundy domination, among other problems for which no suchalgorithm was previously known. Moreover, by proving that fixed powers of bounded degree andbounded treewidth graphs are also bounded degree and bounded treewidth graphs, we can enlarge thefamily of problems that can be solved in polynomial time for these graph classes, including distancecoloring problems and distance domination problems (for bounded distances).