Home

Пятница, 15 мая, 18:00, к. 106

Пятница, 15 мая, комната 106. Начало в 18:00.

Докладчик: Н. Гравин.

Тема: Линейные алгоритмы для задачи списковой $ d $-раскраски и задачи докрашивания частичной $ \Delta $-раскраски.

Abstract

Как известно задача о возможности раскраски произвольного графа
является $ \mathbf{NP}- $полной. Однако, если число допустимых цветов
больше максимальной степени графа, то найти правильную раскраску не
составляет труда. Одной из наиболее общих постановок задач о
раскраске графа, про которую известны какие-либо положительные
результаты, является задача списковой $ d $-раскраски. В этой задаче
нам дан граф, заданный при помощи списка ребер, и даны списки
допустимых цветов для всех вершин этого графа, кроме того, известно,
что длина списка для любой вершины $ v $ по крайней мере $ deg(v) $. В
докладе будет описан линейный по времени и памяти алгоритм для
задачи списковой $ d $-раскраски, который находит правильную раскраску
или выдает, что таковой нет. Используя этот алгоритм можно легко
получить алгоритм для решения задачи дополнения существующей
$ \Delta $-раскраски.