Constructing graph theoretical structures using meta-heuristic algorithms

Through the use of graph theoretical structures, many important operations can be performed on various networks. Dominating set which is one of these structures, has many important applications such as clustering, intrusion detection and backbone formation in wireless sensor networks; placement of gateways in wireless mesh networks; summarizing multiple documents and selecting queries for information retrieval on the internet. Finding the minimum weighted connected dominating set (MWCDS) is an NP-Hard problem. Hence, approximation algorithms and meta-heuristic algorithms can give effective results in polynomial time. Although there are numerous studies related to this subject in the literature, there is no study about finding the MWCDS for undirected graphs using meta-heuristic algorithms. In this thesis study, two different meta-heuristic algorithms are proposed for the MWCDS problem. These algorithms are Hybrid Genetic Algorithm (HGA) and Population-Based Iterated Greedy (PBIG) Algorithm. HGA is a steady-state algorithm that combines a genetic search with a greedy heuristic approach. PBIG algorithm improves the population by applying a deconstruction process and a reconstruction process to each individual in a greedy way. The performances of the proposed algorithms are compared with other greedy heuristics and brute force algorithms. The proposed algorithms performed very well in terms of solution quality and execution time.