Geodesic
Maximum flow in parallel networks with connected arcs
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Voronezh international spring mathematical school "Modern methods of the theory of boundary-value problems. Pontryagin readings—XXXIV", Voronezh, May 3-9, 2023, Part 2, Tome 231 (2024), pp. 44-52.

Voir la notice de l'article provenant de la source Math-Net.Ru

The well-known problem of finding maximum flows in classical networks has many solution algorithms that have a polynomial computational complexity depending on the size of the network. In general, the problem of finding maximum flows for networks with connected arcs is NP-complete. However, among the previously studied networks with connected arcs, there are networks for which the calculation of maximum flows is feasible in a time polynomially depending on the size of the network. This work is devoted to determining the influence of the topology of networks with connected arcs on the possibility of finding maximum flows in polynomial time. In this paper, for a class of parallel networks with connected arcs, we propose a fast polynomial algorithm for finding maximum flows.
Keywords: graph, network, network flow, maximum flow, parallel network, connected arcs, networks with reachability restrictions 
@article{INTO_2024_231_a3,
     author = {I. M. Erusalimskyi and V. A. Skorokhodov and V. A. Rusakov},
     title = {Maximum flow in parallel networks with connected arcs},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {44--52},
     publisher = {mathdoc},
     volume = {231},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2024_231_a3/}
}
TY  - JOUR
AU  - I. M. Erusalimskyi
AU  - V. A. Skorokhodov
AU  - V. A. Rusakov
TI  - Maximum flow in parallel networks with connected arcs
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2024
SP  - 44
EP  - 52
VL  - 231
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2024_231_a3/
LA  - ru
ID  - INTO_2024_231_a3
ER  - 
%0 Journal Article
%A I. M. Erusalimskyi
%A V. A. Skorokhodov
%A V. A. Rusakov
%T Maximum flow in parallel networks with connected arcs
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2024
%P 44-52
%V 231
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2024_231_a3/
%G ru
%F INTO_2024_231_a3
I. M. Erusalimskyi; V. A. Skorokhodov; V. A. Rusakov. Maximum flow in parallel networks with connected arcs. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Voronezh international spring mathematical school "Modern methods of the theory of boundary-value problems. Pontryagin readings—XXXIV", Voronezh, May 3-9, 2023, Part 2, Tome 231 (2024), pp. 44-52. http://geodesic.mathdoc.fr/item/INTO_2024_231_a3/

[1] Vodolazov N. N., Issledovanie statsionarnykh i dinamicheskikh potokov v setyakh bez ogranichenii i s ogranicheniyami na dostizhimost, Diss. na soisk. uch. step. kand. fiz.-mat. nauk., Yaroslavskii gosudarstvennyi universitet im. P. G. Demidova, Yaroslavl, 2010

[2] Erusalimskii Ya. M., Skorokhodov V. A., “Potoki v setyakh so svyazannymi dugami”, Izv. vuzov. Sev.-Kav. reg. Estestv. nauki., 2003, no. 8, 9–12 | Zbl

[3] Kormen T., Leizerson Ch., Rivest R., Shtain K., Algoritmy: postroenie i analiz, Vilyams, M., 2005

[4] Skorokhodov V. A., “Potoki v obobschennykh setyakh so svyazannymi dugami”, Model. anal. inform. sist., 19:2 (2012), 41–52

[5] Erusalimskiy I. M., Rusakov V. A., “Some networks that allow splashes of dynamic flows and finding the maximum splash value”, J. Math. Sci., 271 (2023), 223–-232 | DOI | MR

[6] Ford L. R. Jr., Fulkerson D. R., Flows in Networks, Princeton Univ. Press, Princeton, 2010 | MR

[7] Goldberg A. P., Tarjan R. E., “Efficient maximum flow algorithms”, Commun. ACM., 57:8 (2014), 82–89 | DOI

[8] Newman M., Networks: An Introduction, Oxford Univ. Press, New York, 2010 | MR