A New Approach for Minimum Dominating Set Problem: A Three-Stage Solution with Malatya Centrality Metrics

Authors : Şeyda Karcı, Fatih Okumuş, İhsan Tuğal, Murat Demir, Ali Karci

Pages : 101-115

Doi:10.53070/bbd.1660231

View : 42 | Download : 43

Publication Date : 2025-06-01

Article Type : Research Paper

Abstract :The Minimum Dominating Set (MDS) problem is a fundamental challenge in graph theory, with applications spanning diverse domains. This study introduces a novel three-stage approach for solving the MDS problem, which yields solutions at each stage of the process. Leveraging three fundamental interconnected Malatya centrality methodologies, the approach offers an effective means of addressing MDS across a spectrum of problem scales. These centrality metrics capture the centrality of the target node with its neighbors. The algorithm prioritizes nodes with elevated dominance and clustering in the initial iterations, gradually incorporating those with lower clustering into the dominant cluster in the later stages. Notably, the transaction cost is higher in the early iterations but decreases in the later ones. The empirical assessment spans various problem scenarios, encompassing synthetic datasets generated through a specific approach, examples crafted using the Erdös-Renyi model, and authentic datasets drawn from network science applications. Upon examination, it becomes evident that the proposed algorithm consistently yields robust solutions across diverse constraints. In the majority of cases, the performance of the proposed methods surpasses that of existing related algorithms. The findings of this study contribute to the evolving landscape of MDS problem-solving techniques, offering insights into the most promising avenues for future research and practical applications in network design, resource allocation, and beyond.
Keywords : Minimum Hakim Küme, Hakim Düğüm Sayısı, Merkezilik, Açgözlü Sezgisel Yöntemler, Graf Algoritmaları

ORIGINAL ARTICLE URL