Maximum Flow with Bipartite Matching

Abstract

In this study, the maximum flow problem in all networks that can be modeled on bipartite networks has been solved. The maximum flow problem refers to the maximum flow capacity reached between source and sink nodes on a network. There are different types of approaches to solving the maximum flow problem. One of these popular methods is matching methods. In this study, it is aimed to calculate maximum flow values for bipartite graph types. For the solution, Malatya Matchin algorithm (MMA), which gives optimum matching results in bipartite graphs, was used. MMA gives optimum results in unweighted bipartite graph types. In this study, the application was carried out on unweighted random bipartite graphs produced with the Erdos reyni model and optimum results were achieved. R programming language and igraph library were used to implement the algorithm and design the networks.

Keywords

• Maximum Bipartite Matching
• Maximum Flow
• Malatya Matching Algorithm

İki Parçalı Eşleştirme ile Maksimum Akış

Abstract

Bu çalışmada bipartite ağlar üzerinde modellenebilen tüm ağlardaki maksimum akış probleminin çözümü gerçekleştirilmiştir. Maksimum flow problemi bir ağ üzerindeki source ve sink düğümleri arasında ulaşılan maksimum akış kapasitesini ifade etmektedir. Maksimum flow probleminin çözümü için farklı yaklaşım türleri mevcuttur. Bu popüler yöntemlerden bir tanesi eşleştirme(matching) yöntemleridir. Bu çalışmada bipartite çizge türlerine yönelik maksimum akış değerleri hesaplanması hedeflenmiştir. Çözüm için bipartite çizgelerde optimum matching sonuçlarını veren Malatya Matching algoritması(MMA) kullanılmıştır. MMA ağırlıksız bipartite çizge türlerinde optimum sonucu vermektedir. Bu çalışmada Erdos reyni model ile üretilen ağırlıksız rastgele bipartite çizgelerde uygulama gerçekleştirilmiş ve optimum sonuçlara ulaşılmıştır. Algoritmanın uygulanması ve ağların tasarlanmasında R programlama dili ve igraph kütüphanesi kullanılmıştır.

Keywords

• Maksimum Bipartite Eşleştirme
• Maksimum Akış
• Malatya Matching Algoritması

References

1. [1] Akhmediyarova, A., Kassymova, D., Utegenova, A. & Utepbergenov, I. (2016). Development and research of the algorithm for determining the maximum flow at distribution in the network. Open Computer Science, 6(1), 213-218. https://doi.org/10.1515/comp-2016-0017.
2. [2] Moore, E.J., Kichainukon, W., & Phalavonk, U. (2013). Maximum flow in road networks with speed-dependent capacities – application to Bangkok traffic. Songklanakarin Journal of Science and Technology (SJST), 35, 489-499.
3. [3] Xu Sun, Zixiu Bai, Kun Lin, Pengpeng Jiao and HuaPu Lu, “Optimization Model of Traffic Sensor Layout considering Traffic Big Data ”,Journal of Advanced Transportation,Volume 2020, https://doi.org/10.1155/2020/8845832.
4. [4] Michael G.H. Bell, Fumitaka Kurauchi, Supun Perera, Walter Wong,Investigating transport network vulnerability by capacity weighted spectral analysis,Transportation Research Part B: Methodological,Volume 99,2017,Pages 251-266,https://doi.org/10.1016/j.trb.2017.03.002.
5. [5] Vincenza Torrisi, Matteo Ignaccolo, Giuseppe Inturri, Analysis of road urban transport network capacity through a dynamic assignment model: validation of different measurement methods, Transportation Research Procedia, Volume 27, 2017, Pages 1026-1033, https://doi.org/10.1016/j.trpro.2017.12.135.
6. [6] C. Li, W. Yue, G. Mao and Z. Xu, "Congestion Propagation Based Bottleneck Identification in Urban Road Networks," in IEEE Transactions on Vehicular Technology, vol. 69, no. 5, pp. 4827-4841, May 2020, doi: 10.1109/TVT.2020.2973404.
7. [7] Sreeja Kamishetty, Soumya Vadlamannati, Praveen Paruchuri, Towards a better management of urban traffic pollution using a Pareto max flow approach, Transportation Research Part D: Transport and Environment, Volume 79, 2020, https://doi.org/10.1016/j.trd.2019.11.023.
8. [8] Noraini Abdullah, Ting kien Hua. “Traffic Congestion Problem In Kota Kinabalu , Sabah Using Ford-Fulkerson Algorithm And Max Flow-Min Cut Theorem”, April 2017, International Conference on Business, Tourism & Technology, AnCasa Residence, Port Dickson, Negeri SembilanVolume: 2

9. [9] Yuhong Gao, Zhaowei Qu, Xianmin Song, Zhenyu Yun, Modeling of urban road network traffic carrying capacity based on equivalent traffic flow, Simulation Modelling Practice and Theory, Volume 115, 2022, https://doi.org/10.1016/j.simpat.2021.102462.
10. [10] Anthony Chen, Panatda Kasikitwiwat, Modeling capacity flexibility of transportation networks, Transportation Research Part A: Policy and Practice, Volume 45, Issue 2, 2011, Pages 105-117, https://doi.org/10.1016/j.tra.2010.11.003.
11. [11] R. Ghanbari, M. Jalili and X. Yu, "Analysis of cascaded failures in power networks using maximum flow based complex network approach," IECON 2016 - 42nd Annual Conference of the IEEE Industrial Electronics Society, 2016, pp. 4928-4932, doi: 10.1109/IECON.2016.7793826.
12. [12] Merve Bulut, Evrencan Özcan, Optimization of electricity transmission by Ford–Fulkerson algorithm, Sustainable Energy, Grids and Networks, Volume 28, 2021, https://doi.org/10.1016/j.segan.2021.100544.
13. [13] Y.M. Omar, P. Plapper, Maximum Flow of Complex Manufacturing Networks, Procedia CIRP, Volume 86, 2019, Pages 245-250, https://doi.org/10.1016/j.procir.2020.01.005.
14. [14] Y. -C. Tu, M. C. Chen and Y. S. Sun, "A Two-Stage Link Scheduling Scheme for Variable-Bit-Rate Traffic Flows in Wireless Mesh Networks," in IEEE Transactions on Wireless Communications, vol. 13, no. 11, pp. 6232-6244, Nov. 2014, doi: 10.1109/TWC.2014.2358591.
15. [15] WuChang Wang, Yi Zhang, YuXing Li, Chengsong Liu, Shiying Han, Vulnerability analysis of a natural gas pipeline network based on network flow, International Journal of Pressure Vessels and Piping, Volume 188, 2020, 104236, https://doi.org/10.1016/j.ijpvp.2020.104236.
16. [16] Huai Su, Enrico Zio, Jinjun Zhang, Xueyi Li,A systematic framework of vulnerability analysis of a natural gas pipeline network,Reliability Engineering & System Safety,Volume 175,2018,Pages 79-91,https://doi.org/10.1016/j.ress.2018.03.006.
17. [17]- Zhang Y, Lin H (2021) Perfect matching and distance spectral radius in graphs and bipartite graphs. Discrete Applied Mathematics Volume 304 Pages 315-322. https://doi.org/10.1016/j.dam.2021.08.008
18. [18]- Datta S, Kulkarni R, Tewari R, Vinodchandran NV (2012) Space complexity of perfect matching in bounded genus bipartite graphs. Journal of Computer and System Sciences Volume 78 Issue 3 Pages 765-779. https://doi.org/10.1016/j.jcss.2011.11.002.
19. [19]- Monnot J (2005) The labeled perfect matching in bipartite graphs. Information Processing Letters Volume 96 Issue 3 Pages 81-88. https://doi.org/10.1016/j.ipl.2005.06.009.
20. [20]- Adams P, Mahdian M, Mahmoodian ES (2002) On the forced matching numbers of bipartite graphs. Discrete Mathematics Volume 281 Issues 1–3 Pages 1-12. https://doi.org/10.1016/j.disc.2002.10.002.
21. [21]- Kleinerman S (2006) Bounds on the forcing numbers of bipartite graphs. Discrete Mathematics Volume 306 Issue 1 Pages 66-73. https://doi.org/10.1016/j.disc.2005.11.001.
22. [22] Yong-Qing Cheng, Victor Wu, Robert Collins, Allen R. Hanson, and Edward M. Riseman "Maximum-weight bipartite matching technique and its application in image feature matching", Proc. SPIE 2727, Visual Communications and Image Processing '96, (27 February 1996); https://doi.org/10.1117/12.233261.
23. [23] Cosmin Silvestru Negrucşeri, Mircea BOGDAN Pacsoşi, Barbara Stanley, Clifford Stein, and Cristian George Strat. 2008. Solving maximum flow problems on real-world bipartite graphs. ACM J. Exp. Algorithmics 16, Article 3.5 (2011), 25 pages. https://doi.org/10.1145/1963190.2025381.
24. [24] Muqing Du, Xiaowei Jiang & Anthony Chen (2022) Identifying critical links using network capacity-based indicator in multi-modal transportation networks, Transportmetrica B: Transport Dynamics, 10:1, 1126-1150, DOI: 10.1080/21680566.2021.2023371.
25. [25] İbrahim Akgün, Barbaros Ç. Tansel, R. Kevin Wood, The multi-terminal maximum-flow network-interdiction problem, European Journal of Operational Research, Volume 211, Issue 2, 2011, Pages 241-251, https://doi.org/10.1016/j.ejor.2010.12.011.
26. [26] J. Kleinberg and É. Tardos. Algorithm Design. Pearson Education, 2006, pp. 337–411. isbn: 0-321-29535-8.
27. [27] STINA LÅNGSTRÖM, EMILIA FRIDSÄLL, Optimizing traffic flow on congested roads, STOCKHOLM, SWEDEN 2019, DEGREE PROJECT IN ELECTRONICS AND COMPUTER ENGINEERING, FIRST CYCLE
28. [28] J. Yuan, E. Bae and X. -C. Tai, "A study on continuous max-flow and min-cut approaches," 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2010, pp. 2217-2224, doi: 10.1109/CVPR.2010.5539903.
29. [29]- Carrabs F, Cerulli R, Gentili M (2009) The labeled maximum matching problem. Computers & Operations Research Volume 36 Issue 6 Pages 1859-1871. https://doi.org/10.1016/j.cor.2008.05.012.
30. [30]- Monnot J (2005) On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems. In: Deng X, Du DZ. (eds) Algorithms and Computation ISAAC Lecture Notes in Computer Science vol 3827 Springer Berlin Heidelberg. https://doi.org/10.1007/11602613_93.
31. [31]- Yakut S, Öztemiz F & Karci A (2023) A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm. J Supercomput (2023). https://doi.org/10.1007/s11227-023-05397-8.
32. [32]- Karci A, Yakut S & Öztemiz F (2022) A New Approach Based on Centrality Value in Solving the Minimum Vertex Cover Problem: Malatya Centrality Algorithm. Computer Science Vol:7 (Issue:2) 81-88. https://doi.org/10.53070/bbd.1195501.
33. [33]- Yakut S, Öztemiz F & Karci A (2023) A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm. Computer Science Vol:8 (Issue:1) 16-23. https://doi.org/10.53070/bbd.1224520.
34. [34]- Cengiz Hark, Ali Karcı, Karcı summarization: A simple and effective approach for automatic text summarization using Karcı entropy, Information Processing & Management, Volume 57, Issue 3, 2020, https://doi.org/10.1016/j.ipm.2019.102187.