Proceedings of International Conference on Applied Innovation in IT
2023/11/30, Volume 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


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.

DOI: 10.25673/112988

Download: PDF

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.


    HOME

       - Call for Papers
       - Paper Submission
       - For authors
       - Important Dates
       - Conference Committee
       - Editorial Board
       - Reviewers
       - Last Proceedings


    PROCEEDINGS

       - Volume 12, Issue 1 (ICAIIT 2024)        - Volume 11, Issue 2 (ICAIIT 2023)
       - Volume 11, Issue 1 (ICAIIT 2023)
       - Volume 10, Issue 1 (ICAIIT 2022)
       - Volume 9, Issue 1 (ICAIIT 2021)
       - Volume 8, Issue 1 (ICAIIT 2020)
       - Volume 7, Issue 1 (ICAIIT 2019)
       - Volume 7, Issue 2 (ICAIIT 2019)
       - Volume 6, Issue 1 (ICAIIT 2018)
       - Volume 5, Issue 1 (ICAIIT 2017)
       - Volume 4, Issue 1 (ICAIIT 2016)
       - Volume 3, Issue 1 (ICAIIT 2015)
       - Volume 2, Issue 1 (ICAIIT 2014)
       - Volume 1, Issue 1 (ICAIIT 2013)


    PAST CONFERENCES

       ICAIIT 2024
         - Photos
         - Reports

       ICAIIT 2023
         - Photos
         - Reports

       ICAIIT 2021
         - Photos
         - Reports

       ICAIIT 2020
         - Photos
         - Reports

       ICAIIT 2019
         - Photos
         - Reports

       ICAIIT 2018
         - Photos
         - Reports

    ETHICS IN PUBLICATIONS

    ACCOMODATION

    CONTACT US

 

DOI: http://dx.doi.org/10.25673/115729


        

         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


           ISSN 2199-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 - Red Building, Top floor, Room 425, Bernburger Str. 55, D-06366 Köthen, Germany

        site traffic counter

Creative Commons License
Except where otherwise noted, all works and proceedings on this site is licensed under Creative Commons Attribution-ShareAlike 4.0 International License.