Адрес e-mail:

Изоморфизм графов (Д.В. Мусатов, М.И. Тихомиров, весна 2016)

Лекторы — доц. Д.В. Мусатов, М.И. Тихомиров

Спецкурс будет проходит по средам с 17:05 до 18:30 в ауд. 511ГК. Первое занятие — 24 февраля.

Анонс

Задача об изоморфизме двух графов — редкий пример задачи, для которой не известно ни полиномиального алгоритма, ни доказательства NP-полноты. В декабре 2015 года Ласло Бабаи объявил о создании квазиполиномиального алгоритма, т.е. работающего за O(n^polylog(n)) шагов. В первой половине курса мы изучим известные частные случаи, для которых задача решается быстро: деревья, графы ограниченной степени, планарные графы и др., — и поговорим о месте задачи в иерархии сложностных классов. Во второй половине курса мы попробуем разобраться в алгоритме, предложенном Бабаи.


Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li soc-yt
Яндекс.Метрика