Positioning Security Cameras in The Central Transportation Networks of Barcelona With Minimum Cost via The Malatya Minimum Vertex Cover Algorithm

Yıl 2024, Cilt: 5 Sayı: 2, 77 - 85, 31.12.2024

Cemalettin Sonakalan , Furkan Öztemiz

https://doi.org/10.54047/bibted.1545238

Öz

The Minimum Vertex Cover issue (MVCP) is a significant NP-complete optimization issue in graph theory. Its objective is to find a set of nodes that covers all edges of a given graph and contains the minimum number of nodes. Many different approaches and algorithms have been tried for this issue. Nevertheless, as the MVCP problem is an optimization problem, solutions are usually non-heuristic and only work under certain constraints Moreover, the proposed methods do not achieve the expected effect and the solution sets may change with each iteration. Having a minimum number of nodes in a network with a minimum coverage area improves network efficiency, reduces energy consumption, and allows for more efficient resource utilization. This study aims to control all streets in a popular neighborhood in Barcelona with a minimum number of security cameras. The Malatya Vertex Cover method is used to locate the optimal number of security cameras around the area. For modeling, the area is transformed into a graph using Google Earth. Each intersection represents a node. The graph was modeled using R programming language. Then, with the Malatya Vertex Cover algorithm, the Malatya centrality values of the nodes of the graph will be calculated. This centrality value is obtained from the sum of the ratio of the degree of each node to the degree of its neighbors. For the MVCP solution, the node of the graph with the highest Malatya centrality value is selected and added to the solution set. Then, this node and its edge links are removed from the graph. When the edges are completely covered, the process is terminated. As a result of this analysis, a low-cost solution is achieved by using the minimum number of security cameras to cover the entire region.

Anahtar Kelimeler

Minimum Vertex Cover, Security Cameras, Graph Theory, Malatya Centrality

Positioning Security Cameras in The Central Transportation Networks of Barcelona With Minimum Cost via The Malatya Minimum Vertex Cover Algorithm

Öz

Minimum Vertex Cover Problemi (MVCP), çizge teorisinde önemli bir NP-complete optimizasyon problemidir. Amacı, verilen bir grafın tüm kenarlarını kapsayan ve en az sayıda düğüm içeren bir düğüm kümesini bulmaktır. Bu problem için birçok farklı yaklaşım ve algoritma denenmiştir. Ancak MVCP problemi bir optimizasyon problemi olduğundan, çözümler genellikle sezgisel olmayıp belirli kısıtlamalar altında sonuç vermektedir. Bir ağda düğümlerin en az sayıda kapsanması, ağın verimliliğini yükseltir, enerji tüketimini düşürür ve kaynakların daha veriml, kullanılmasını sağlar. Bu çalışma, Barcelona şehrinde popüler bir muhitteki cadde ve sokakların tümünü en az sayıda güvenlik kamerasıyla kontrol edilmesini hedefler. Bölge Google Earth kullanılarak çizgeye uygun modellenmiştir. Her bir kavşak bir düğümü temsil etmektedir. R programlama dili kullanılarak çizge oluşturulmuştur. Ardından Malatya Vertex Cover algoritmasıyla, çizgenin düğümlerinin Malatya merkezilik değerleri hesaplanacaktır. Bu merkezilik değeri her bir düğümün derecesinin, komşularının derecesine oranının toplamından elde edilmektedir. MVCP çözümü için ise, çizgenin en yüksek Malatya merkezilik değerine sahip olan düğümü seçilerek çözüm kümesine eklenir. Sonrasında, bu düğüm ve kenar bağlantıları çizgeden çıkarılır. Kenarlar tamamen kapsandığında, işlem sonlandırılır. Bu analiz sonucunda tüm bölgeyi kapsayacak şekilde en az sayıda güvenlik kamerası kullanarak düşük maliyetli çözüm sağlanmıştır.

Anahtar Kelimeler

Minimum Vertex Cover, Security Cameras, Graph Theory, Malatya Centrality

Kaynakça

• Thulasiraman, K., Swamy, M, NS. (2011). Graphs: theory and algorithms. Montreal: John Wiley & Sons.
• Hark, C., Karcı, A. (2022). A new multi-document summarisation approach using saplings growing-up optimisation algorithms : Simultaneously optimised coverage and diversity. https://doi.org/10.1177/01655515221101841.
• Thulasiraman, K., Arumugam, S., Brandstädt, A., and Nishizeki, T. (2016). Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, Boca Raton: Chapman & Hall/CRC.
• Khattab, H., Mahafzah, B, A., and Sharieh, A. (2022). A hybrid algorithm based on modified chemical reaction optimization and best-first search algorithm for solving minimum vertex cover problem. Neural Comput. Appl., vol. 34(18), pp. 15513–15541, https://doi.org/10.1007/s00521-022-07262-w.
• Dinur, I., and Safra, S. (2005). On the hardness of approximating vertex cover. Ann. Math. 162(1), 439–485, https://doi.org/10.4007/annals.2005.162.439.
• Angel, D. (2022). Protection of Medical Information Systems Against Cyber Attacks: A Graph Theoretical Approach. Wirel. Pers. Commun., 126(4), 3455–3464, https://doi.org/10.1007/s11277-022-09873-x
• Wang, L., Du, W., Zhang, Z., and Zhang, X. (2017). A PTAS for minimum weighted connected vertex cover P3 problem in 3-dimensional wireless sensor networks. J. Comb. Optim., 33(1), 106–122. https://doi.org/10.1007/s10878-015-9937-z
• Hossain, A. (2020). Automated design of thousands of nonrepetitive parts for engineering stable genetic systems. Nat. Biotechnol., 38(12), 1466–1475. https://doi.org/10.1038/s41587-020-0584-2
• Gusev, V, V. (2020). The vertex cover game: Application to transport networks. Omega, 97, 102102. https://doi.org/10.1016/j.omega.2019.08.009
• Dagdeviren, Z., A. (2021). Weighted Connected Vertex Cover Based Energy-Efficient Link Monitoring for Wireless Sensor Networks Towards Secure Internet of Things. IEEE Access, 9, 10107–10119. https://doi.org/10.1109/ACCESS.2021.3050930
• Yigit, Y., Dagdeviren, O., and Challenger, M. (2022). Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks. Sensors, 22(10), 3774. https://doi.org/10.3390/s22103774
• Yigit Y., Dagdeviren, Z. A., Dagdeviren, O., and Challenger, M. (2021). Performance Evaluation of Capacitated Vertex Cover Algorithms for Security Applications in Wireless Sensor Networks. in 7th International Conference on Electrical, Electronics and Information Engineering: Technological Breakthrough for Greater New Life, ICEEIE. https://doi.org/10.1109/ICEEIE52663.2021.9616719
• Yigit, Y., Akram, V. K., and Dagdeviren, O. (2021) Breadth-first search tree integrated vertex cover algorithms for link monitoring and routing in wireless sensor networks. Comput. Networks, 194, 108144. https://doi.org/10.1016/j.comnet.2021.108144
• Dagdeviren, Z. A. (2022) A Metaheuristic algorithm for vertex cover based link monitoring and backbone formation in wireless Ad hoc Networks. Expert Syst. Appl., 213(PA), 118919. https://doi.org/10.1016/j.eswa.2022.118919.
• Öztemiz, F., Karci, A. (2021). Malatya İli ulaşım ağı kavşak noktalarının Merkezlilik Analizi. Gazi Üniversitesi Mühendislik Mimarlık Fakültesi Dergisi 37(1),511-528. https://doi.org/10.17341/gazimmfd.834255
• Yigit, Y., Dagdeviren, O., and Challenger, M., (2022). Self-Stabilizing Capacitated Vertex Cover Algorithms for Internet-of-Things-Enabled Wireless Sensor Networks. Sensors, 22(10), 3774. https://doi.org/10.3390/s22103774 Hebatulla,h K., Sharieh, A. (2019). Most Valuable Player Algorithm for Solving Minimum Vertex Cover Problem. Basel A. January 2019International Journal of Advanced Computer Science and Applications 10(8) https://doi.org/10.14569/IJACSA.2019.0100821
• Guo, Quan, and Chen (2019). achieved significant success in solving the Minimum Vertex Cover problem using the Membrane Evolutionary Algorithm (MEAMVC)
• Xiaojun, X., Xiaolin, Q., Chunqiang, Y., Xingye, X. (2018). Test-cost-sensitive rough set based approach for minimum weight vertex cover problem. Applied Soft Computing, 64, 423-435. https://doi.org/10.1016/j.asoc.2017.12.023
• Jovanovic. R., Sanfilippo, AP., & Voß, S. (2022). Fixed set search applied to the multi-objective minimum weighted vertex cover problem. Journal of Heuristics, 28(4), 481–508. https://doi.org/10.1007/s10732-022-09499-z
• Li, R., Hu, S., Cai, S., Gao, J., Wang, Y., & Yin, M. (2019). NuMWVC: A novel local search for minimum weighted vertex cover problem. Journal of the Operational Research Society, 71(9), 1498–1509. https://doi.org/10.1080/01605682.2019.1621218 Yakut, S., Öztemiz, F., & Karci A. (2023). A new robust approach to solve minimum vertex cover problem: Malatya vertex-cover algorithm. J Supercomput 79, 19746–19769 https://doi.org/10.1007/s11227-023-05397-8
• 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, 7(2), 81-88. https://doi.org/10.53070/bbd.1195501
• 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, 8(1), 16-23. https://doi.org/10.53070/bbd.122452
• Goldberg, M., Hollinger, D., Magdon-Ismail, M. (2005). Experimental Evaluation of the Greedy and Random Algorithms for Finding Independent Sets in Random Graphs. In: Nikoletseas, S.E. (eds) Experimental and Efficient Algorithms. WEA 2005. Lecture Notes in Computer Science, 3503. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11427186_44
• Alipour, S., & Salari, M. (2022). Brief announcement: Distributed algorithms for minimum dominating set problem and beyond, a new approach. In 36th International Symposium on Distributed Computing (DISC 2022), 246, 40:1-40:3. https://doi.org/10.4230/LIPIcs.DISC.2022.40