Тестирование свойств графа в модели плотных графов (Святослав Грязнов)

Пятница, 28 октября 2016, 19:00–20:20
ПОМИ РАН, аудитория 106

Описание

Рассмотрим модель плотных графов. Предложим алгоритмы полиномиальной запросовой сложности для задачи проверки графа на регулярность, а также для класса задач, связанных с разбиением графа (например, k-раскрашиваемость, поиск максимальной клики).