Proposing a centrality-based solution method for the paired dominating set problem in graphs

Graph theory plays an important role in engineering applications. Many scientific and engineering-based problems are commonly modeled as network structures and analyzed using graph-theoretical approaches. However, many problems in graph theory are classified as NP-hard or NP-complete, and therefore cannot generally be solved in polynomial time. Various approaches have been proposed to obtain efficient solutions for such problems. In this thesis, an optimal deterministic algorithm is proposed. Centrality metrics are utilized in the construction of the paired dominating set, and a solution is presented that determines a primary leader node for each pair along with a secondary node acting as its backup (standby) node. The proposed method has been applied to networks with various sizes and structural properties, and nearly full coverage has been achieved in almost all cases. In other words, every node outside the selected set is adjacent to at least one node belonging to the set.Furthermore, the proposed approach demonstrates efficiency in terms of time complexity, particularly for large-scale networks.