phone +7 (3412) 91 60 92
mail imi@udsu.ru
ru-RU Russian
Home » Issues » Archive of Issues » 2021 - 3 issue » pp. 458-470

Archive of Issues

Russia Rostov-on-Don
Year
2021
Volume
31
Issue
3
Pages
458-470
<<
>>
Section Mathematics
Title Flows in strongly regular periodic dynamic resource networks
Author(-s) Skorokhodov V.A.a, Sviridkin D.O.a
Affiliations Southern Federal Universitya
Abstract This paper is devoted to studying the processes of resource allocation in dynamic resource networks. In such networks, the capacities of the arcs depend on time. Resource allocation in the network occurs in discrete time. The resource of each vertex is distributed only between adjacent vertices according to some rules. The study of the processes of resource redistribution in such networks is carried out. The main goal is to develop methods for finding the limit state (distribution) of a resource in a dynamic resource network. It is shown that the approach based on the construction of an auxiliary network is also applicable to reduce the problem of resource allocation in a dynamic network to a similar problem in an auxiliary network. Theorems on the existence of a limit state on an auxiliary graph are proved for strongly regular periodic dynamical networks. To find the limit states, one can use the approaches which are developed for the shortest path problem in dynamic networks.
Keywords resource network, dynamic networks, threshold value, process of resources allocation, limit state in resource network
UDC 519.1
MSC 05C21, 05C90
DOI 10.35634/vm210308
Received 9 September 2020
Language Russian
Citation Skorokhodov V.A., Sviridkin D.O. Flows in strongly regular periodic dynamic resource networks, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2021, vol. 31, issue 3, pp. 458-470.
References
  1. Ford L.R., Fulkerson D.R. Constructing maximal dynamic flows from static flows, Operations Research, 1958, vol. 6, issue 3, pp. 419-433. https://doi.org/10.1287/opre.6.3.419
  2. Aronson J.E. A survey of dynamic network flows, Annals of Operations Research, 1989, vol. 20, issue 1, pp. 1-66. https://doi.org/10.1007/BF02216922
  3. Erzin A.I., Takhonov I.I. Equilibrium resource distribution in a network model, Journal of Applied and Industrial Mathematics, 2007, vol. 1, issue 3, pp. 293-302. https://doi.org/10.1134/S1990478907030052
  4. Fonoberova M., Lozovanu D. The maximum flow in dynamic networks, Computer Science Journal of Moldova, 2004, vol. 12, no. 3 (36), pp. 387-396. http://www.math.md/publications/csjm/issues/v12-n3/7570/
  5. Fonoberova M., Lozovanu D. The minimum cost multicommodity flow problem in dynamic networks and an algorithm for its solving, Computer Science Journal of Moldova, 2005, vol. 13, no. 1 (37), pp. 29-36. http://www.math.md/publications/csjm/issues/v13-n1/8518/
  6. Klinz B., Woeginger G.J. One, two, three, many, or: complexity aspects of dynamic network flows with dedicated arcs, Operations Research Letters, 1998, vol. 22, issues 4-5, pp. 119-127. https://doi.org/10.1016/S0167-6377(98)00009-1
  7. Orlin J.B. Maximum-throughput dynamic network flows, Mathematical Programming, 1983, vol. 27, issue 2, pp. 214-231. https://doi.org/10.1007/BF02591946
  8. Skorokhodov V.A., Chebotareva A.S. The maximum flow problem in a network with special conditions of flow distribution, Journal of Applied and Industrial Mathematics, 2015, vol. 9, no. 3, pp. 435-446. https://doi.org/10.1134/S199047891503014X
  9. Erusalimskii Ya.M., Skorokhodov V.A., Kuz'minova M.V., Petrosyan A.G. Grafy s nestandartnoi dostizhimost'yu: zadachi, prilozheniya (Graphs with non-standard reachability: problems, application), Rostov-on-Don: Southern Federal University, 2009.
  10. Skorokhodov V.A. Flows on graphs with varying transit times through the arcs, Izvestiya Vysshikh Uchebnykh Zavedenii. Severo-Kavkazskii Region. Ser. Estestvennye nauki, 2011, no. 1 (161), pp. 21-26 (in Russian). https://elibrary.ru/item.asp?id=15622169
  11. Kuz'minova M.V. Periodic dynamic graphs. Maximum flow problem, Izvestiya Vysshikh Uchebnykh Zavedenii. Severo-Kavkazskii Region. Ser. Estestvennye nauki, 2008, no. 1 (143), pp. 14-19 (in Russian). https://elibrary.ru/item.asp?id=9989543
  12. Kuznetsov O.P., Zhilyakova L.Yu. Nonsymmetric resource networks. The study of limit states, Management and Production Engineering Review, 2011, vol. 2, no. 3, pp. 33-39.
  13. Kuznetsov O.P., Zhilyakova L.Yu. Bidirectional resource networks: A new flow model, Doklady Mathematics, 2010, vol. 82, no. 1, pp. 643-646. https://doi.org/10.1134/S1064562410040368
  14. Zhilyakova L.Yu. Asymmetrical resource networks. I. Stabilization processes for low resources, Automation and Remote Control, 2011, vol. 72, no. 4, pp. 798-807. https://doi.org/10.1134/S0005117911040102
  15. Zhilyakova L.Yu. Ergodic cyclic resource networks. I. Oscillations and equilibrium at low resources, Upravlenie Bol'shimi Sistemami, 2013, issue 43, pp. 34-54 (in Russian). http://mi.mathnet.ru/eng/ubs673
  16. Zhilyakova L.Yu. Ergodic cyclic resource networks. II. High levels of resource, Upravlenie Bol'shimi Sistemami, 2013, issue 45, pp. 6-29 (in Russian). http://mi.mathnet.ru/eng/ubs715
  17. Skorokhodov V.A., Abdulrahman H. Dynamic resource networks. The case of small resource, Vestnik Voronezhskogo Gosudarstvennogo Universiteta. Ser. Fizika. Matematika, 2018, no. 4, pp. 186-194 (in Russian). https://elibrary.ru/item.asp?id=36516098
  18. Novikov F.A. Diskretnaya matematika (Discrete mathematics), Saint Petersburg: Piter, 2013.
  19. Gantmacher F.R. The theory of matrices. Vol. 1, 2., Providence, RI: AMS, 2000.
  20. Skorokhodov V.A. Stability and stationary distribution on graphs with non-standard reachability, Izvestiya Vysshikh Uchebnykh Zavedenii. Severo-Kavkazskii Region. Ser. Estestvennye nauki, 2007, no. 4 (140), pp. 17-21 (in Russian). https://elibrary.ru/item.asp?id=13052922
  21. Skorokhodov V.A. The problem of finding the threshold value in ergodic resource network, Upravlenie Bol'shimi Sistemami, 2016, issue 63, pp. 6-23 (in Russian). http://mi.mathnet.ru/eng/ubs886
Full text
/doc/issues-2021/21-03-08.pdf
<< Previous article
Next article >>