MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem

Basit Öğe Kaydı
dc.contributor.authorOkumus, Fatih
dc.contributor.authorKarci, Seyda
dc.date.accessioned2026-04-04T13:31:14Z
dc.date.available2026-04-04T13:31:14Z
dc.date.issued2024
dc.departmentİnönü Üniversitesi
dc.description.abstractThe graph theory is one of the fundamental structures in computer science used to model various scientific and engineering problems. Many problems within the graph theory are categorized as NP-hard and NP-complete. One such problem is the minimum dominating set (MDS) problem, which seeks to identify the minimum possible subsets in a graph such that every other node in the subset is directly connected to a node in this subset. Due to its inherent complexity, developing an efficient polynomial-time method to address the MDS problem remains a significant challenge in graph theory. This paper introduces a novel algorithm that utilizes a centrality measure known as the Malatya Centrality to effectively address the MDS problem. The proposed algorithm, called the Malatya Dominating Set Algorithm (MDSA), leverages centrality values to identify dominating sets within a graph. It extends the Malatya centrality by incorporating a second-level centrality measure, which enhances the identification of dominating nodes. Through a systematic and algorithmic approach, these centrality values are employed to pinpoint the elements of the dominating set. The MDSA uniquely integrates greedy and dynamic programming strategies. At each step, the algorithm selects the most optimal (or near-optimal) node based on the centrality values (greedy approach) while updating the neighboring nodes' criteria to influence subsequent decisions (dynamic programming). The proposed algorithm demonstrates efficient performance, particularly in large-scale graphs, with time and space requirements scaling proportionally with the size of the graph and its average degree. Experimental results indicate that our algorithm outperforms existing methods, especially in terms of time complexity when applied to large datasets, showcasing its effectiveness in addressing the MDS problem.
dc.identifier.doi10.3390/app14209251
dc.identifier.issn2076-3417
dc.identifier.issue20
dc.identifier.orcid0000-0003-3046-9558
dc.identifier.scopus2-s2.0-85207357006
dc.identifier.scopusqualityQ1
dc.identifier.urihttps://doi.org/10.3390/app14209251
dc.identifier.urihttps://hdl.handle.net/11616/108672
dc.identifier.volume14
dc.identifier.wosWOS:001341533500001
dc.identifier.wosqualityQ2
dc.indekslendigikaynakWeb of Science
dc.indekslendigikaynakScopus
dc.language.isoen
dc.publisherMdpi
dc.relation.ispartofApplied Sciences-Basel
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı
dc.rightsinfo:eu-repo/semantics/openAccess
dc.snmzKA_WOS_20250329
dc.subjectminimum dominating set problem
dc.subjectgraph theory
dc.subjectgraph centrality
dc.subjectgreedy approach
dc.subjectdynamic programming
dc.titleMDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem
dc.typeArticle

Dosyalar

Koleksiyon

WoS İndeksli Yayınlar Koleksiyonu
Scopus İndeksli Yayınlar Koleksiyonu