Proceedings of International Conference on Applied Innovation in IT  ·  2023/11/30  ·  Vol. 11  ·  Issue 2  ·  pp. 1–10
Inverse and Direct Maxflow Problem Study on the Free-Oriented ST-Planar Network Graph
Victor Tikhonov, Serhii Nesterenko, Abdullah Taher, Olena Tykhonova, Olexandra Tsyra, Olha Yavorska and Kateryna Shulakova
📄 Download PDF DOI: 10.25673/112988
Abstract
The issues of telecommunication network engineering are considered in the context of digital flows optimal scheduling. Introduced the concept of the free-oriented network graph as an enhanced math model of the modern software defined networking technologies with dynamic channel configuration. Normalized the framework of ST-planar network graph for the MaxFlow problem analysis. Formulated the inverse and direct tasks of network MaxFlow problem on the ST-planar free-oriented network graph concerning conventional Ford-Fulkerson approach and SDN virtual infrastructure design respectively. The inverse MaxFlow problem is formalized in terms of discrete optimization on Pontryagin maximum principle. The direct MaxFlow problem exhibited as graph templates generation combinatorial procedure by alternative criteria of flow paths shortest lengths or maximal diversity of paths. Specified the terms of "topology" and "metrics" for open twopole software defined network in the form of vertices' relation matrix, along with the tensors of ST-paths and ST-flows. The properties of planar graph have been studied as functions of vertices number, including the edges quantity, ST-flows tensor dimensions and paths' length distribution. The direct MaxFlow problem formalism can be used for automated testing the algorithms of classical inverse MaxFlow task, as well as generation the comprehensive teaching sequence for artificial intellect machine learning
Keywords
Telecommunication Network Maximal Flow Free Oriented Planar Graph SDN.
References
  1. L.R. Ford and D.R. Fulkerson, "Maximal flow through a network," Canadian Journal of Mathematics, vol. 8, 1956, pp. 399-404. [Online]. Available: https://www.semanticscholar.org/paper/ Maximal-Flow-Through-a-Network-Ford-Fulkerson/794b01b2513f3610cb151ecfd07e9dc0eae7e1f3.
  2. Y. Dinitz, "Algorithm for solution of a problem of maximum flow in a network with power estimation," 1970. [Online]. Available: https://www.researchgate.net/publication/228057696_Algorithm_for_Solution_of_a_Problem_of_Maximum_Flow_in_Networks_with_Power_Estimation.
  3. J. Edmonds and R. Karp, "Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems," Journal of the Association for Computing Machinery, vol. 19, no. 2, 1972, pp. 248-264.
  4. J.A. Bondy, et al., "Graph theory with applications," Macmillan Press Ltd, GB, 1976. [Online]. Available: https://www.iro.umontreal.ca/
  5. A.V. Goldberg and R.E. Tarjan, "A new approach to the maximum flow problem," Proceedings of the eighteenth annual ACM symposium on Theory of computing – STOC '86, 1986, pp. 136-146.
  6. A. V. Goldberg and S. Rao, "Beyond the flow decomposition barrier," J. ACM, vol. 45, no. 5, 1998, pp. 783-797.
  7. D. Papp, "The Goldberg-Rao algorithm for the maximum flow problem," COS 528 class notes, 2006, 5 p. [Online]. Available: https://www.cs.princeton.edu/courses/archive/fall06/cos528/handouts/Goldberg-Rao.pdf.
  8. P. Christiano, et al., "Electrical Flows, Laplacian Systems, and Faster Approximation of Maximum Flow in Undirected Graphs," Computer Science, Data Structures and Algorithms, 2010. [Online]. Available: https://www.semanticscholar.org/reader/af1afe809c106ed2618fc2ae14b696f672fc4bc1.
  9. M.A. Rajouh, "Osobenosti primenenia princip maximuma Pontryagin," BNTU, 2013. [Online]. Available: https://rep.bntu.by/bitstream/handle/data /5527/Osobennosti_primenenie.pdf?sequence=1&isAllowed=y.
  10. D.P. Williamson, "Network flow algorithms," Cornell University, 2019. [Online]. Available: https://www.networkflowalgs.com/book.pdf.
  11. O.V. Tykhonova, et al., "The Max-Flow Problem Statement on the Three-Pole Open Network Graph," 2019 3rd International Conference on Advanced Information and Communications Technologies (AICT), Lviv, Ukraine, 2019, pp. 209-212, doi: 10.1109/AIACT.2019.8847745. [Online]. Available: https://ieeexplore.ieee.org/document/ 8847745/metrics#metrics.
  12. O.V. Tykhonova, "Conveyor-modular method of multimedia flows integration with delay control in packet based telecommunication network," PhD Dissertation, O.S.Popov ONAT, Odessa, 2019.
  13. R. Haese et al., "Algorithms and Complexity for the Almost Equal Maximum Flow Problem," Operations Research Proceedings 2019. Springer, Cham, 2020, pp. 323-329.
  14. A. Alzaben, et al., "End-to-End Routing in SDN Controllers Using Max-Flow Min-Cut Route Selection Algorithm," 23rd International Conference on Advanced Communication Technology (ICACT), 2021, pp. 461-467.
  15. H. Liu, et al., "Optimization of a logistics transportation network based on a genetic algorithm," Hindawi Mobile Information Systems, vol. 2022, 2022, pp. 167-176. [Online]. Available: https://doi.org/10.1155/2022/1271488.
  16. O. Cruz-Mejía and A.N. Letchford, "A survey on exact algorithms for the maximum flow and minimum-cost flow problems," Networks, vol. 82, no. 2, 2023. [Online]. Available: https://onlinelibrary.wiley.com/doi/full/10.1002/net.22169.
  17. Y. Bengio, et al., "Machine learning for combinatorial optimization: A methodological tour d’horizon," European Journal of Operational Research, vol. 290, no. 2, 2021, pp. 405-421.
  18. B. Mor, et al., "Heuristic algorithms for solving a set of NP-hard single-machine scheduling problems with resource-dependent processing times," Computers & Industrial Engineering, vol. 153, 2021.
  19. W. Jiang, "Graph-based Deep Learning for Communication Networks: A Survey," Computer Communications, vol. 185, 2022, pp. 40-54. [Online]. Available: https://www.sciencedirect.com/science/article/abs/pii/S0140366421004874?via%3Dihub.
  20. N. Orkun Baycik, "Machine learning based approaches to solve the maximum flow network interdiction problem," Computers & Industrial Engineering, vol. 167, 2022.
  21. T. Tawanda, et al., "An intelligent node labelling maximum flow algorithm," Int J Syst Assur Eng Manag 14, pp. 1276-1284, 2023. [Online]. Available: https://doi.org/10.1007/s13198-023-01930-3.
  22. "Graph theory," Britannica, 2023. [Online]. Available: https://www.britannica.com/topic/graph-theory.
  23. L. Wagner, "Complete Python Tutorial for Absolute Beginners," 2023.
  24. A. Kuronya, "Introduction to topology," 2010, 102 p.
  25. Matrix calculator. [Online]. Available: https://matrixcalc.org.

Proceedings of the International Conference on Applied Innovations in IT by Anhalt University of Applied Sciences is licensed under CC BY-SA 4.0  ·  This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

ICAIIT 2026
International Conference on Applied Innovation in IT
Navigation
Publisher
ISSN2199-8876
Publisher Edition Hochschule Anhalt
Location Anhalt University of Applied Sciences
Email leiterin.hsb@hs-anhalt.de
Phone +49 (0) 3496 67 5611
Address Building 01, Room 425
Bernburger Str. 55
D-06366 Köthen, Germany
Open Access License
CC BY-SA 4.0

All works are licensed under the Creative Commons Attribution-ShareAlike 4.0 International License (CC BY-SA 4.0), unless otherwise noted.

Published by ICAIIT in cooperation with Anhalt University of Applied Sciences.

© 2026 ICAIIT — International Conference on Applied Innovations in IT. Anhalt University of Applied Sciences, Köthen, Germany.
Visitors: site traffic counter