Calculating the Centrality Values According to the Strengths of Entities Relative to their Neighbours and Designing a New Algorithm for the Solution of the Minimal Dominating Set Problem

Authors : Şeyda Karci, Fatih Okumuş, Ali Karci

Pages : 50-56

Doi:10.53070/bbd.1295038

View : 38 | Download : 50

Publication Date : 2023-06-08

Article Type : Research Article

Abstract :The dominating set problem in graph theory is an NP-complete problem for an arbitrary graph. There are many approximation-based studies in the literature to solve the dominating set problems for a given graph. Some of them are exact algorithms with exponential time complexities and some of them are based on approximation without robustness with respect to obtained solutions. In this study, the Malatya centrality value was used and a new Malatya centrality value was defined to solve the dominating set problem for a given graph. The improved algorithms have polynomial time and space complexities.
Keywords : Dominating Set, Malatya Centrality Value, Graph Theory, NP-Complete Problem