УДК 519.17
О новых алгоритмических приемах для задачи о взвешенной вершинной раскраске
О. О. Развенская1
| Аннотация | Классическая NP-трудная задача о взвешенной вершинной раскраске состоит в минимизации количества цветов в раскрасках вершин задаваемого графа так, что для каждой вершины назначаются цвета, количество которых равно задаваемому весу вершины, причем смежным вершинам назначаются различные цвета. Соответствующее наименьшее количество цветов называется взвешенным хроматическим числом графа. Известно несколько полиномиальных алгоритмических приемов для построения эффективных алгоритмов для задачи о взвешенной вершинной раскраске. Например, стандартными приемами такого рода являются модульное разложение графов и разложение графов посредством разделяющих клик. В данной статье предлагаются новые полиномиальные способы редукции графов в форме удаления избыточных вершин и пересчета весов остальных вершин так, что взвешенное хроматическое число изменяется контролируемым образом. Приводится способ сведения задачи о взвешенной вершинной раскраске к ее невзвешенному варианту и его приложение. Эта работа вносит вклад в алгоритмическую теорию графов. |
|---|---|
| Ключевые слова | задача о взвешенной вершинной раскраске, эффективный алгоритм, вычислительная сложность |
1Развенская Ольга Олеговна, аспирант, кафедра прикладной математики и информатики, ФГАОУ ВО «НИУ ВШЭ» , (603155, Россия, г. Нижний Новгород, ул. Большая Печерская, д. 25/12), ORCID: http://orcid.org/ 0000-0002-1440-9910, olga-olegov@yandex.ru
Цитирование: Развенская О. О. О новых алгоритмических приемах для задачи о взвешенной вершинной раскраске // Журнал Средневолжского математического общества. 2020. Т. 22, № 4. С. 442–448.
DOI 10.15507/2079-6900.22.202004.442-448
