Графы ограниченной степени и тестирование их свойств (Надежда Воронова)
Семинар по сублинейным алгоритмам


Что: Лекция
Когда: Пятница, 18 ноября 2016, 19:00–20:20
Где:

Описание

Введём модель графов с ограничением на степень вершины и рассмотрим тестирование некоторых свойств, таких как свобода от подграфов, регулярность графа, эйлеровость, связность и \(t\)-связность. Также, если останется время, докажем некоторые нижние оценки на сложность некоторых тестеров.