Volume 22, No 3, 2015, P. 55-74
UDC 519.1
Skorokhodov V. A., Chebotareva A. S.
The maximal flow problem on networks with special conditions of flow distribution
Abstract:
We consider the problem of finding the maximal flow in nets with conditions of strict and nonstrict flow distribution. We show that for each condition of flow distribution the solution of the considered problem exists and is unique. The algorithms for finding the maximal flow are developed for each condition of flow distribution.We find bounds on the maximal flow value in the case of strict flow distribution.
Ill. 3, tab. 4, bibliogr. 27.
Keywords: network, graph, graph algorithm, maximal flow on network, flow distribution.
DOI: 10.17377/daio.2015.22.455
Vladimir A. Skorokhodov 1
Anastasia S. Chebotareva 1
1. Southern Federal University,
8a Milchakova St., 344090 Rostov-on-Don, Russia
e-mail: pdvaskor@yandex.ru, chebot1988@yandex.ru
Received 16 June 2014
Revised 25 March 2015
References
[1] A. I. Erzin and I. I. Takhonov, The problem of the search for a balanced flow, Sib. Zh. Ind. Mat., 9, No. 4, 50–63, 2006.[2] Ya. M. Erusalimsky and N. N. Vodolazov, Unsteady flow in a network, Vestn. Don. Gos. Tekh. Univ., 9, No. 3, 402–409, 2009.
[3] Ya. M. Erusalimsky, V. A. Skorokhodov, M. V. Kuzminova, and A. G. Petrosyan, Grafy s nestandartnoi dostizhimost’yu: zadachi, prilozheniya (Graphs with Nonstandard Connectivity: Problems and
Applications), Yuzh. Fed. Univ., Rostov-on-Don, 2009.
[4] O. P. Kuznetsov and L. Yu. Zhilyakova, Bidirectional resource networks: A new flow model, Dokl. Akad. Nauk, 433, No. 5, 609–612, 2010. Translated in Dokl. Math., 82, No. 1, 643–646, 2010.
[5] A. G. Kurosh, Kurs vysshei algebry, Nauka, Moscow, 1975. Translated under the title Higher Algebra, Mir, Moscow, 1975.
[6] V. A. Skorokhodov, Flows on graphs with varying transit times through the arcs, Izv. VUZ. Sev.-Kavk. Reg., Ser. Estestv. Nauki, No. 1, 21–26, 2011.
[7] V. A. Skorokhodov, Flows in generalized nets with related arcs, Model. Anal. Inf. Sist., 19, No. 2, 41–52, 2012.
[8] L. R. Ford and D. R. Fulkerson, Flows in Networks, Princeton Univ. Press, Princeton, 1962.
[9] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Upper Saddle River, USA, 1993.
[10] M. Fonoberova, On determining the minimum cost flows in dynamic networks, Bul. Acad. ¸Stiin¸te Repub. Mold., Mat., No. 1., 51–56, 2006.
[11] A. V. Goldberg and S. Rao, Beyond the flow decomposition barrier, J. ACM, 45, No. 5, 783–797, 1998.
