Проблема изоморфизма графов

Общая информация
ЛекторИ. Н. Пономаренко
Семестросень 2010
Дата начала10.10.2010
Количество пар10
Язык курсарусский
Lecture notes
Видеоhttp://lektorium.tv/course/?id=22782
Аннотация
  • Постановка. Задачи, эквивалентные проблеме изоморфизма графов. Изоморфно полные классы.
  • Каноническая форма. Вероятностный алгоритм распознавания изоморфизма графов за полиномиальное время.
  • Распознавание изоморфизма деревьев и планарных графов.
  • Алгебраические леса и алгоритм Вейсфейлера-Лемана.
  • Почти-полиномиальные алгоритмы распознавания изоморфизма графов и других комбинаторных структур.
  • Алгоритмы для работы с группами перестановок (орбиты, принадлежность, порядок, стабилизаторы).
  • Распознавание изоморфизма графов с ограниченными цветными классами. Неэффективность комбинаторных алгоритмов.
  • Алгоритм Лакса для кубических графов. Графы ограниченной степени.
  • Умеренно экспоненциальный алгоритм распознавания изоморфизма графов (Бабаи-Земляченко).
  • Циркулянтные графы.
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

Ваша оценка: Пусто Средняя: 5 (1 голос)
Share |
Илья Николаевич Пономаренко
Илья Николаевич Пономаренко
Илья Николаевич Пономаренко и студенты