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


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

Описание

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