Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Математическое моделирование транспортных потоков
17 ноября 2012 г., г. Москва
 


Быстрые алгоритмы разложения потоков

М. А. Бабенкоab

a Яндекс
b Московский государственный университет им. М. В. Ломоносова, механико-математический факультет

Количество просмотров:
Эта страница:343
Youtube:



Аннотация: Пусть задана направленная сеть с двумя источниками $s_1$, $s_2$, одним стоком $t$ и потоком $f$ в ней. Тогда несложно заметить, что $f$ можно разложить в сумму $f_1 + f_2$ двух потоков: первый из $s_1$ в $t$, а другой — из $s_2$ в $t$. Подобные разложения встречаются в качестве подзадачи в ряде алгоритмов комбинаторной оптимизации. Насколько быстро их можно построить?
Используя стандартный метод разложения потока на элементарные (вдоль простых путей и циклов) эту задачу можно найти за время $O(VE)$. Эта оценка, однако, далека от оптимальной. На докладе будут обсуждаться более быстрые алгоритмы, имеющие сложность, близкую к линейной. Все они основаны на известной из комбинаторики идее отщепления (splitting), позволяющей обратимым образом упростить граф сети.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024