Laboratory of Mathematical Logic at PDMI

Пятница, 30 декабря, ауд. 106. Начало в 16:00.

Докладчик: Светлана Образцова.

Тема: Алгоритмы для нахождения k-robust разрезов.

Abstract

Доклад будет посвящен k-robust разрезам, то есть таким разрезам сети, что любой путь ведущий из истока в сток, пересекает разрез по крайней мере k раз. Будет описана структура таких разрезов и различные полиномиальные алгоритмы их нахождения, в том числе и комбинаторный. Так же будет рассмотрено естественное обобщение этой задачи и полиномиальный алгоритм для него. В задаче есть открытые вопросы, которые могут заинтересовать любителей теории графов и комбинаторных алгоритмов.

Доклад планируется элементарный, не требующий особых предварительных знаний в размерах больших, чем теорема Форда-Фалкерсона. Хотя может оказаться полезным знание терминов "метод эллипсоидов" и "separation oracle". Доклад основан на совместной работе докладчика и Николая Гравина.