Research Article
BibTex RIS Cite

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

Year 2023, Volume: Vol:8 Issue: Issue:2, 102 - 109, 20.12.2023
https://doi.org/10.53070/bbd.1386446

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.

References

  • [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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]- 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]- 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]- 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]- 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]- 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] 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] 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] 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] İ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] J. Kleinberg and É. Tardos. Algorithm Design. Pearson Education, 2006, pp. 337–411. isbn: 0-321-29535-8.
  • [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] 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]- 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]- 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]- 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]- 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]- 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]- 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.

Maximum Flow with Bipartite Matching

Year 2023, Volume: Vol:8 Issue: Issue:2, 102 - 109, 20.12.2023
https://doi.org/10.53070/bbd.1386446

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.

References

  • [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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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]- 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]- 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]- 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]- 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]- 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] 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] 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] 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] İ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] J. Kleinberg and É. Tardos. Algorithm Design. Pearson Education, 2006, pp. 337–411. isbn: 0-321-29535-8.
  • [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] 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]- 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]- 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]- 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]- 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]- 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]- 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.
There are 34 citations in total.

Details

Primary Language Turkish
Subjects Algorithms and Calculation Theory
Journal Section PAPERS
Authors

Furkan Öztemiz 0000-0001-5425-3474

Publication Date December 20, 2023
Submission Date November 5, 2023
Acceptance Date December 1, 2023
Published in Issue Year 2023 Volume: Vol:8 Issue: Issue:2

Cite

APA Öztemiz, F. (2023). İki Parçalı Eşleştirme ile Maksimum Akış. Computer Science, Vol:8(Issue:2), 102-109. https://doi.org/10.53070/bbd.1386446

The Creative Commons Attribution 4.0 International License 88x31.png is applied to all research papers published by JCS and

A Digital Object Identifier (DOI) Logo_TM.png is assigned for each published paper