Efficient Algorithm for Dominating Set in Graph Theory Based on Fundamental Cut-Set

Basit Öğe Kaydı
dc.authorscopusid57200139801
dc.authorscopusid6602929072
dc.contributor.authorOztemiz F.
dc.contributor.authorKarci A.
dc.date.accessioned2024-08-04T20:03:32Z
dc.date.available2024-08-04T20:03:32Z
dc.date.issued2024
dc.departmentİnönü Üniversitesien_US
dc.description.abstractDetermining 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.en_US
dc.identifier.doi10.35378/gujs.1243008
dc.identifier.endpage652en_US
dc.identifier.issn2147-1762
dc.identifier.issue2en_US
dc.identifier.scopus2-s2.0-85196194627en_US
dc.identifier.scopusqualityQ3en_US
dc.identifier.startpage636en_US
dc.identifier.urihttps://doi.org/10.35378/gujs.1243008
dc.identifier.urihttps://hdl.handle.net/11616/91908
dc.identifier.volume37en_US
dc.indekslendigikaynakScopusen_US
dc.language.isoenen_US
dc.publisherGazi Universitesien_US
dc.relation.ispartofGazi University Journal of Scienceen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectDominant Nodeen_US
dc.subjectDominating Seten_US
dc.subjectGraph Theoryen_US
dc.subjectKarci Centralityen_US
dc.subjectKMax Treeen_US
dc.titleEfficient Algorithm for Dominating Set in Graph Theory Based on Fundamental Cut-Seten_US
dc.typeArticleen_US

Dosyalar

Koleksiyon

Scopus İndeksli Yayınlar Koleksiyonu