Positioning Security Cameras in The Central Transportation Networks of Barcelona With Minimum Cost via The Malatya Minimum Vertex Cover Algorithm
Ö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
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