ОБ ОСОБЕННОСТЯХ ПОТОКА В СЕТЯХ С БАРЬЕРНОЙ ДОСТИЖИМОСТЬЮ
Аннотация
Рассматривается задача о нахождении максимального потока в сетях с барьерной достижимостью при помощи модифицированного алгоритма Эдмондса-Карпа. Особенность предложенного алгоритма в том, что он позволяет находить поток в сетях, для которых разработанный ранее алгоритм [1] не находил решения.
Список литературы
1. Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами./Я.М.Ерусалимский, В.А.Скороходов.//Изв. вузов. Сев.-Кав. регион. Естественные науки, 2003; прил. № 8. -С. 9-12.
2. 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.
3. Ning Xuanxi, Ning Angelika The Blocking Flow Theory and its Application to Hamiltonian Graph Problems. Germany,Aachen: Shaker Verlag GmbH, 2006. -249p.
Для цитирования:
ВОДОЛАЗОВ Н. ОБ ОСОБЕННОСТЯХ ПОТОКА В СЕТЯХ С БАРЬЕРНОЙ ДОСТИЖИМОСТЬЮ. Вестник Донского государственного технического университета. 2008;8(2):127-136.
For citation:
VODOLAZOV N. On the flow peculiarity in network with barrier reachability. Vestnik of Don State Technical University. 2008;8(2):127-136. (In Russ.)
Просмотров: 25
Послать статью по эл. почте 