Graph Isomorphism Problem, autumn 2010

Graph Isomorphism Problem
Saint Petersburg / autumn 2010, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Постановка. Задачи, эквивалентные проблеме изоморфизма графов. Изоморфно полные классы.
Каноническая форма. Вероятностный алгоритм распознавания изоморфизма графов за полиномиальное время.
Распознавание изоморфизма деревьев и планарных графов.
Алгебраические леса и алгоритм Вейсфейлера-Лемана.
Почти-полиномиальные алгоритмы распознавания изоморфизма графов и других комбинаторных структур.
Алгоритмы для работы с группами перестановок (орбиты, принадлежность, порядок, стабилизаторы).
Распознавание изоморфизма графов с ограниченными цветными классами. Неэффективность комбинаторных алгоритмов.
Алгоритм Лакса для кубических графов. Графы ограниченной степени.
Умеренно экспоненциальный алгоритм распознавания изоморфизма графов (Бабаи-Земляченко).
Циркулянтные графы.

Date and time	Class\|Name	Venue\|short	Materials
10 October 11:15–12:50	Проблема изоморфизма простых графов, Lecture	ПОМИ РАН	video
10 October 13:00–14:35	Изоморфно-полные классы и категории, Lecture	ПОМИ РАН	video
24 October 13:00–14:35	Проблемы, эквивалентные проблеме изоморфизма, Lecture	ПОМИ РАН	video
31 October 11:15–12:50	Комбинаторные алгоритмы, Lecture	ПОМИ РАН	video
31 October 13:00–14:35	Алгоритмы для групп перестановок, Lecture	ПОМИ РАН	video
28 November 11:15–12:50	Алгоритм Симса, Lecture	ПОМИ РАН	video
28 November 13:00–14:35	Распознавание изоморфизма кубических графов, Lecture	ПОМИ РАН	video
05 December 15:35–17:10	Умеренно-экспоненциальный алгоритм распознавания изоморфизма, Lecture	ПОМИ РАН	video
12 December 11:15–12:50	Алгоритм Вейсфейлера-Лемана, Lecture	ПОМИ РАН	video
12 December 13:00–14:35	Когерентные конфигурации, Lecture	ПОМИ РАН	video