Location of wireless sensor networks using graph theory based method

This thesis focuses on the Minimum Vertex Cover Problem (MVCP) and explores the optimization capabilities of graph theory through two distinct application areas, presenting an innovative approach. MVCP is an NP-hard problem that aims to find a set of vertices covering all edges of a graph with the minimum number of vertices. With a wide range of applications in areas such as network design, communication networks, and social networks, MVCP plays a critical role in improving energy efficiency and optimizing resource usage. In this study, cost-effective and applicable solutions have been developed using the Malatya Vertex Cover algorithm. The first application proposes a solution to cover a neighborhood in Barcelona with the minimum number of security cameras. Intersections within the neighborhood were modeled as vertices, and the dataset obtained via Google Earth was transformed into a graph using the R programming language. The Malatya Vertex Cover algorithm calculated the centrality values of vertices, iteratively selecting those with the highest centrality values to include in the solution set. This method effectively minimized security costs while covering the entire area. The second application focuses on the optimal placement of wireless access points within the campus of Inonu University. The university buildings were marked as vertices in a graph model created using Google Earth. The Malatya Vertex Cover algorithm determined the selection of vertices, resulting in a network design that covered the entire campus with the minimum number of access points. This analysis achieved cost savings and energy efficiency. In both application areas, the effectiveness and applicability of the Malatya Vertex Cover method were demonstrated. The findings highlight the potential of graph theory-based optimization methods to provide practical solutions to real-world problems, contributing significantly to the existing literature.