?
Эффективная разрешимость задачи о взвешенной вершинной раскраске для некоторых двух наследственных классов графов
Задача о взвешенной вершинной раскраске для заданного взвешенного графа состоит в том, чтобы минимизировать количество используемых цветов так, что для каждой вершины количество назначаемых ей цветов равно ее весу и назначаемые множества цветов для любых смежных вершин не пересекаются. Для всех наследственных классов, определяемых двумя связными 5-вершинными порожденными запретами, кроме четырех случаев, известна вычислительная сложность варианта задачи о взвешенной вершинной раскраске с единичными весами. Для четырех из шести попарных пересечений данных четырех классов ранее была доказана разрешимость задачи о взвешенной вершинной раскраске за полиномиальное от суммы весов вершин время. Для оставшихся двух таких пересечений данный факт устанавливается в настоящей работе.