Com­pa­ring Ex­is­t­ing Me­thods to Ef­fi­­cient­ly Place Dro­nes to Con­nect Iso­la­ted Com­mu­n­i­ca­ti­on Clus­ters

Drones are increasingly used in diverse scenarios, from disaster response to temporary communication support in isolated networks. 
This thesis investigates a theoretical framework in which drones act as communication pathways to connect separated local networks, abstracted as nodes in a two-dimensional Euclidean space.
Nodes with a certain proximity can freely communicate forming connected components (CC), while connecting distant nodes incurs a cost proportional to the distance, representing the usage of drones.
We address two sub-problems: identifying nodes that can communicate via free edges (connectivity) and determining which additional edges are needed to enable communication between all nodes (minimum spanning tree, MST). 
We also consider a dynamic setting, where node movement causes network connections to change over time.
For dynamic connectivity, we implemented a baseline breadth-first search, a forest-based approach, and an Euler tour tree method, and we also describe a more advanced top-tree approach. 
While for the MST problem we implemented one dynamic approach as well as two approximation approaches with slight variations.
We evaluated the algorithms on networks with up to 200 nodes, varying node density, placement patterns, grid sizes, and CC counts. 
Performance largely depends on the number and size of connected components. 
For dynamic connectivity, Lazy CC performs best for small CCs, while Euler tour trees excel with larger CCs. 
For MSTs, dynamic algorithms outperform Kruskal as CC count increases, and approximation algorithms achieve significant speedups for some additional cost.
Overall, our results provide a systematic experimental analysis of dynamic connectivity and MST algorithms in abstract drone network scenarios and offer guidance for selecting algorithms depending on network characteristics.