Efficient Algorithm for Dominating Set in Graph Theory Based on Fundamental Cut-Set
Küçük Resim Yok
Tarih
2024
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Gazi Universitesi
Erişim Hakkı
info:eu-repo/semantics/openAccess
Özet
Determining the minimum dominating set in connected graphs is one of the most difficult problems defined as NP-hard. In this problem, it is aimed to determine the important nodes that can influence all nodes via the minimum number of nodes on the graph. In this study, an efficient near-optimal algorithm showing a deterministic approach has been developed different from the approximation algorithms mentioned in the literature for discovering dominating set. The algorithm has O(n3) time complexity in determining the Dominating Set (DS). At the same time, the algorithm is an original algorithm whose solution is not random by using a fundamental cut-set. The DS algorithm consists of 3 basic phases. In the first phase of the algorithm, the algorithm that constructs the special spanning tree (Karci Max tree) of the graph is developed. In the second phase, the algorithm that finds the fundamental cut sets using the Kmax spanning tree is developed. In the last phase, Karci centrality node values are calculated with fundamental cut set and by using these Karci centrality node values, an algorithm has been developed to identify DS nodes. As a result of these three phases, the dominance values of the nodes on the graph and the DS nodes are calculated. The detected Karci centrality node values give priority to the node selection for determining the DS. All phases of the developed DS and Efficient node algorithms were coded in R programming language and the results were examined by running on sample graphs. © 2024, Gazi Universitesi. All rights reserved.
Açıklama
Anahtar Kelimeler
Dominant Node, Dominating Set, Graph Theory, Karci Centrality, KMax Tree
Kaynak
Gazi University Journal of Science
WoS Q Değeri
Scopus Q Değeri
Q3
Cilt
37
Sayı
2
