Mathematical Logic and Discrete Mathematics at PDMI

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

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

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

Abstract

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