Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English
Computer Science Club

Проблема изоморфизма графов
Санкт-Петербург / осень 2010, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти
  • Постановка. Задачи, эквивалентные проблеме изоморфизма графов. Изоморфно полные классы.
  • Каноническая форма. Вероятностный алгоритм распознавания изоморфизма графов за полиномиальное время.
  • Распознавание изоморфизма деревьев и планарных графов.
  • Алгебраические леса и алгоритм Вейсфейлера-Лемана.
  • Почти-полиномиальные алгоритмы распознавания изоморфизма графов и других комбинаторных структур.
  • Алгоритмы для работы с группами перестановок (орбиты, принадлежность, порядок, стабилизаторы).
  • Распознавание изоморфизма графов с ограниченными цветными классами. Неэффективность комбинаторных алгоритмов.
  • Алгоритм Лакса для кубических графов. Графы ограниченной степени.
  • Умеренно экспоненциальный алгоритм распознавания изоморфизма графов (Бабаи-Земляченко).
  • Циркулянтные графы.
Дата и время Занятие Место Материалы
10 октября
11:15–12:50		 Проблема изоморфизма простых графов, Лекция ПОМИ РАН видео
10 октября
13:00–14:35		 Изоморфно-полные классы и категории, Лекция ПОМИ РАН видео
24 октября
13:00–14:35		 Проблемы, эквивалентные проблеме изоморфизма, Лекция ПОМИ РАН видео
31 октября
11:15–12:50		 Комбинаторные алгоритмы, Лекция ПОМИ РАН видео
31 октября
13:00–14:35		 Алгоритмы для групп перестановок, Лекция ПОМИ РАН видео
28 ноября
11:15–12:50		 Алгоритм Симса, Лекция ПОМИ РАН видео
28 ноября
13:00–14:35		 Распознавание изоморфизма кубических графов, Лекция ПОМИ РАН видео
05 декабря
15:35–17:10		 Умеренно-экспоненциальный алгоритм распознавания изоморфизма, Лекция ПОМИ РАН видео
12 декабря
11:15–12:50		 Алгоритм Вейсфейлера-Лемана, Лекция ПОМИ РАН видео
12 декабря
13:00–14:35		 Когерентные конфигурации, Лекция ПОМИ РАН видео
Computer Science Club, 2007–24 гг.