Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 09.12.2007, 13:05
Новичок

Отправить личное сообщение для maksay Посмотреть профиль Найти все сообщения от maksay
 
Регистрация: 15.11.2007
Сообщений: 24

Быстрый алгоритм нахождения макспотока..
Слышал, что можно очень просто реализовать нахождение потока за О(V*E)..
Для этого вроде как надо при поиске в ширину от истока к стоку найти множество всех дополняющих путей - и в графе этих путей протолкнуть наибольший возможный добавочный поток...Правда ли, что этот алгоритм работает за О(V*E)?
  #2  
Старый 09.12.2007, 14:17
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

http://algolist.ru/maths/graphs/maxflows/
  #3  
Старый 09.12.2007, 21:20
гость

 
Сообщений: n/a

Сообщение от maksay Посмотреть сообщение
Слышал, что можно очень просто реализовать нахождение потока за О(V*E)..
Очень соневанию. По моему существование алгоритма в общем случае с такой сложностью еще открытый вопрос.

Если E=Theta(V^2), то алгоритм relabel-to-front имеет сложность O(V^3) = O(VE).

Цитата:
Для этого вроде как надо при поиске в ширину от истока к стоку найти множество всех дополняющих путей - и в графе этих путей протолкнуть наибольший возможный добавочный поток...
Похоже на алгоритм Диница, но его оценка O(V^2 E) -- O(V) фаз, в каждой из которых находится за O(VE) максимальное множество дополняющих путей в подграфе сети, полученной поиском в ширину.
  #4  
Старый 10.12.2007, 20:12
Новичок

Отправить личное сообщение для maksay Посмотреть профиль Найти все сообщения от maksay
 
Регистрация: 15.11.2007
Сообщений: 24

А почему множество всех увеличивающих путей на ходится за О(VE)?..По идее - простым поиком в глубину/ширину за О(Е)...Или я чего то недопонимаю...
  #5  
Старый 11.12.2007, 02:16
гость

 
Сообщений: n/a

Сообщение от maksay Посмотреть сообщение
А почему множество всех увеличивающих путей на ходится за О(VE)?..По идее - простым поиком в глубину/ширину за О(Е)...
Если пропускные способности ребер единицы (ну или, вообще, небольшие константы), то тогда можно и за O(E).
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Супер быстрый поворот изображения Shveya Обработка изображений, звук, графика 10 13.09.2007 15:13
Самый быстрый способ закрасить треугольник Riasoft Обработка изображений, звук, графика 1 01.08.2007 02:40
алгоритм нахождения минимального множества сечений контуров обратной связи ikro Графы 0 03.05.2007 11:00
необходим быстрый алгоритм Spets Математические алгоритмы 0 31.01.2007 20:39
численные методы нахождения целичесленных решений dabeat_bf Математические алгоритмы 1 29.01.2007 14:32