Search
Семинар 28 ноября 2005 года
Понедельник, 28 ноября, комната 106. Начало в 16:30.
Докладчик: М. Бабенко.
Тема: Теория кососимметрических и двунаправленных графов: задачи, алгоритмы и приложения.
Abstract
На докладе будет рассказано про два (эквивалентных) класса нестандартных графов: двунаправленные графы, которые были введены в обращение Эдмондсом (Edmonds) и Джонсоном (Johnson) при изучении определенного класса задач целочисленного программирования, и кососимметрические графы, определение которых сформулировал Татт (Tutte), стремясь предложить унифицированную теорию потоков и паросочетаний. Оба этих понятия появились в 70-х годах прошлого века, а затем изучались в работах Кокэя (Cocay) и Стоуна (Stone), Гольдберга (Goldberg) и Карзанова (Karzanov) и др.
Одним из наиболее значимых достижений данной теории можно считать альтернативную формулировку алгоритма со сложностью O(E*sqrt{V}) для нахождения максимального паросочетания в графе произвольного вида. Впервые такая оценка была достигнута в работе Микали (Micali) и Вазирани (Vazirani), однако их доказательство корректности было чрезвычайно сложным, и в нем нельзя было указать параллелей с уже существующими техниками. Теория кососимметрических потоков позволила восполнить этот пробел: основанный на ней алгоритм является прямым аналогом метода блокирующего потока Диница (Dinic) для двудольных графов.
Изучение кососимметрических и двунаправленных графов в настоящее время преследует несколько целей. С одной стороны, данная теория позволяет кратко и емко описать очень широкий класс задач классической комбинаторной оптимизации (паросочетания, факторы, T-джойны, системы непересекающихся циклов, целочисленные мультипотоки и т.п.). С другой стороны, подобный обобщающий статус подталкивает к идее изучения кососимметрических задач безотносительно существования соответствующих классических аналогов. На докладе будет сформулирован ряд таких задач, а также кратко рассказано об имеющихся результатах.