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

Authors : Cemalettin Sonakalan, Furkan Öztemiz

Pages : 77-85

Doi:10.54047/bibted.1545238

View : 98 | Download : 103

Publication Date : 2024-12-31

Article Type : Research Paper

Abstract :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.
Keywords : Minimum Vertex Cover, Security Cameras, Graph Theory, Malatya Centrality