Search
Семинар 28 апреля 2006 года
Пятница, 28 апреля, комната 106. Начало в 17:30.
Докладчик: П. Г. Зограф.
Тема: Симметрические тензоры и перечислительные задачи теории графов.
Abstract
Предлагается универсальный подход к перечислительным задачам теории графов, основанный на сворачивании тензоров в вершинах по ребрам графа. В качестве примеров перечисляются регулярные подграфы (в.т.ч. факторы, гамильтоновы циклы, совершенные паросочетания), реберные раскраски и пр. Обсуждается проблема вычислительной сложности полученных алгоритмов.