Goal: Partitioning Random Geometric Graphs into Bipartite Subgraphs
This is an academic project from Algorithm Engineering course at Southern Methodist University TX. In this project, I have:
- Implemented an algorithm that models ad-hoc networks of wireless sensors of varying scale across a variety of geographic areas.
- Modeled these networks by creating random geometric graphs (RGG) of varying size, degree and type and interconnecting vertices if they are within a maximum broadcast range of one another.
- Determined a bipartite subgraph of the overall RGG, or sensor network, that adequately covers all vertices that make up the overall network.
I have included a detailed report on this in the repository. It is an interesting project and covers many fundamental topics in Algorithms such as Bipartite graphs, Graph-coloring, BFS/DFS.
The entire code is in WSN.py