Пятница, 15 мая, комната 106. Начало в 18:00.
Докладчик: Н. Гравин.
Тема: Линейные алгоритмы для задачи списковой
-раскраски и задачи докрашивания частичной
-раскраски.
Abstract
Как известно задача о возможности раскраски произвольного графа
является
![$ \mathbf{NP}- $](../../../sites/default/files/tex/b4a41e3496b8b3dcaff72462757a3d314494600b/index.png)
полной. Однако, если число допустимых цветов
больше максимальной степени графа, то найти правильную раскраску не
составляет труда. Одной из наиболее общих постановок задач о
раскраске графа, про которую известны какие-либо положительные
результаты, является задача списковой
![$ d $](../../../sites/default/files/tex/f5efd7e164b692a1c06faa4659d1c840d8761de8/index.png)
-раскраски. В этой задаче
нам дан граф, заданный при помощи списка ребер, и даны списки
допустимых цветов для всех вершин этого графа, кроме того, известно,
что длина списка для любой вершины
![$ v $](../../../sites/default/files/tex/e0638f0ad1f77275b64c201dcd60947f3338b8dd/index.png)
по крайней мере
![$ deg(v) $](../../../sites/default/files/tex/060c8b9ee84044850a051863ccb5a15c0a770757/index.png)
. В
докладе будет описан линейный по времени и памяти алгоритм для
задачи списковой
![$ d $](../../../sites/default/files/tex/f5efd7e164b692a1c06faa4659d1c840d8761de8/index.png)
-раскраски, который находит правильную раскраску
или выдает, что таковой нет. Используя этот алгоритм можно легко
получить алгоритм для решения задачи дополнения существующей
![$ \Delta $](../../../sites/default/files/tex/0841840d088e8238c94bd18005ac15f3ca75bbe2/index.png)
-раскраски.