Об особенностях потока в сетях с барьерной достижимостью
Автор: Водолазов Николай Николаевич
Журнал: Advanced Engineering Research (Rostov-on-Don) @vestnik-donstu
Рубрика: Управление, вычислительная техника и информатика
Статья в выпуске: 2 (37) т.8, 2008 года.
Бесплатный доступ
Рассматривается задача о нахождении максимального потока в сетях с барьерной достижимостью при помощи модифицированного алгоритма Эдмондса-Карпа. Особенность предложенного алгоритма в том, что он позволяет находить поток в сетях, для которых разработанный ранее алгоритм [1] не находил решения.
Сеть, источник, сток, поток, блокирующий поток
Короткий адрес: https://sciup.org/14249174
IDR: 14249174 | УДК: 519.1
On the flow peculiarity in network with barrier reachability
The problem of finding maximal flow in networks with barrier reachability is considered. It is shown that existing algorithm for solution this problem can't find solution for all networks. New algorithm is suggested.
Список литературы Об особенностях потока в сетях с барьерной достижимостью
- Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами./Я.М.Ерусалимский, В.А.Скороходов.//Изв. вузов. Сев.-Кав. регион. Естественные науки, 2003; прил. № 8. -С. 9-12.
- Edmonds Jack, Karp Richard M. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems.//Journal of the Association for Computing Machinery. -Vol. 19. -No. 2, April 1972, -P. 248-264.
- Ning Xuanxi, Ning Angelika The Blocking Flow Theory and its Application to Hamiltonian Graph Problems. Germany,Aachen: Shaker Verlag GmbH, 2006. -249p.
