Analytical Validation of the Malatya Dominating Set Algorithm: Constructing Optimal Dominating Sets Without Redundant Nodes

Şeyda Karcı; Fatih Okumuş

Makale detayları

Analytical Validation of the Malatya Dominating Set Algorithm: Constructing Optimal Dominating Sets Without Redundant Nodes

Yazarlar:

Şeyda Karcı | Fatih Okumuş

Yayıncı:

Mus Alparslan University

Ana Başlıklar:

Yazılım Mühendisliği (Diğer)

Dergi:

Muş Alparslan Üniversitesi Fen Bilimleri Dergisi Vol.13 Issue 1, pp.46-56

Belge Tipi:

Makale

Yayın Tarihi:

6/2025

Belge Dili:

İngilizce

Document ID (Org No.):

2001351623

pISSN:

2147-7930

Anahtar kelimeler:

Özet:

 This study focuses on the theoretical proof of the Malatya Dominating Set Algorithm MDSA. MDSA is a dominating set determination algorithm that combines greedy and dynamic programming techniques by using the concept of centrality and thus produces optimum or near-optimum solutions. In the previous study, the MDSA algorithm has been experimentally implemented on various datasets and successful results have been obtained. However, these experimental successes need to be proven analytically with theoretical evidence. For this purpose, in this study, it is analytically proven that MDSA produces optimum or near-optimum results on some special graph types paths, cycles, star graphs, two-sided graphs, etc.. In the study, it is examined in detail how MDSA produces the minimum dominant set when applied to specific graph structures. In the proof process, it is mathematically shown how centrality calculations affect the selection of dominating set and how the algorithm produces redundant-free dominating set by eliminating unnecessary nodes. In conclusion, this study strengthens the theoretical foundations of MDSA and analytically demonstrates its advantages in certain graph types when compared to other dominating set algorithms in the literature.

 This study focuses on the theoretical proof of the Malatya Dominating Set Algorithm MDSA. MDSA is a dominating set determination algorithm that combines greedy and dynamic programming techniques by using the concept of centrality and thus produces optimum or near-optimum solutions. In the previous study, the MDSA algorithm has been experimentally implemented on various datasets and successful results have been obtained. However, these experimental successes need to be proven analytically with theoretical evidence. For this purpose, in this study, it is analytically proven that MDSA produces optimum or near-optimum results on some special graph types paths, cycles, star graphs, two-sided graphs, etc.. In the study, it is examined in detail how MDSA produces the minimum dominant set when applied to specific graph structures. In the proof process, it is mathematically shown how centrality calculations affect the selection of dominating set and how the algorithm produces redundant-free dominating set by eliminating unnecessary nodes. In conclusion, this study strengthens the theoretical foundations of MDSA and analytically demonstrates its advantages in certain graph types when compared to other dominating set algorithms in the literature.

 This study focuses on the theoretical proof of the Malatya Dominating Set Algorithm MDSA. MDSA is a dominating set determination algorithm that combines greedy and dynamic programming techniques by using the concept of centrality and thus produces optimum or near-optimum solutions. In the previous study, the MDSA algorithm has been experimentally implemented on various datasets and successful results have been obtained. However, these experimental successes need to be proven analytically with theoretical evidence. For this purpose, in this study, it is analytically proven that MDSA produces optimum or near-optimum results on some special graph types paths, cycles, star graphs, two-sided graphs, etc.. In the study, it is examined in detail how MDSA produces the minimum dominant set when applied to specific graph structures. In the proof process, it is mathematically shown how centrality calculations affect the selection of dominating set and how the algorithm produces redundant-free dominating set by eliminating unnecessary nodes. In conclusion, this study strengthens the theoretical foundations of MDSA and analytically demonstrates its advantages in certain graph types when compared to other dominating set algorithms in the literature.

 Bu çalışma, Malatya Hâkim Küme Algoritmasının MDSA teorik ispatına odaklanmaktadır. MDSA, merkezilik kavramını kullanarak açgözlü ve dinamik programlama tekniklerini birleştiren ve böylece optimum veya optimuma yakın çözümler üreten bir hâkim küme belirleme algoritmasıdır. Önceki çalışmada, MDSA algoritması çeşitli veri kümeleri üzerinde deneysel olarak uygulanmış ve başarılı sonuçlar elde edilmiştir. Ancak bu deneysel başarıların teorik kanıtlarla analitik olarak ispatlanması gerekmektedir. Bu amaçla, bu çalışmada, MDSAnın bazı özel graf tiplerinde yollar, döngüler, yıldız graflar, iki taraflı graflar vb. optimum veya optimuma yakın sonuçlar ürettiği analitik olarak ispatlanmıştır. Çalışmada, MDSAnın belirli graf yapılarına uygulandığında minimum hâkim kümeyi nasıl ürettiği detaylı olarak incelenmiştir. İspat sürecinde, merkezilik hesaplamalarının hâkim küme seçimini nasıl etkilediği ve algoritmanın gereksiz düğümleri eleyerek nasıl artık düğümlerden arındırılmış hâkim küme ürettiği matematiksel olarak gösterilmiştir. Sonuç olarak, bu çalışma MDSAnın teorik temellerini güçlendirmekte ve literatürdeki diğer baskın küme algoritmalarıyla karşılaştırıldığında belirli grafik tiplerinde avantajlarını analitik olarak ortaya koymaktadır.

Makale detayları

Analytical Validation of the Malatya Dominating Set Algorithm: Constructing Optimal Dominating Sets Without Redundant Nodes

Yazarlar:

Şeyda Karcı | Fatih Okumuş

Yayıncı:

Mus Alparslan University

Ana Başlıklar:

Yazılım Mühendisliği (Diğer)

Dergi:

Muş Alparslan Üniversitesi Fen Bilimleri Dergisi Vol.13 Issue 1, pp.46-56

Belge Tipi:

Makale

Yayın Tarihi:

6/2025

Belge Dili:

İngilizce

Document ID (Org No.):

2001351623

pISSN:

2147-7930

Dominating Sets

Malatya Centrality Value

Malatya Dominating Set Algorithm

Greedy Algorithms

Dynamic Programming

Theoretical ProofHâkim Kümeler

Malatya Merkeziyet Değeri

Malatya Hâkim Küme Algoritması

Açgözlü Algoritmalar

Dinamik Programlama

Teorik İspat

Sayı

Makale detayları

Yazarlar: Şeyda Karcı | Fatih Okumuş

Yayıncı: Mus Alparslan University

Ana Başlıklar: Yazılım Mühendisliği (Diğer)

Dergi: Muş Alparslan Üniversitesi Fen Bilimleri Dergisi Vol.13 Issue 1, pp.46-56

Belge Tipi: Makale

Yayın Tarihi: 6/2025

Belge Dili: İngilizce

Document ID (Org No.): 2001351623

pISSN: 2147-7930

Sayı

Yazarlar:

Şeyda Karcı | Fatih Okumuş

Yayıncı:

Mus Alparslan University

Ana Başlıklar:

Yazılım Mühendisliği (Diğer)

Dergi:

Muş Alparslan Üniversitesi Fen Bilimleri Dergisi Vol.13 Issue 1, pp.46-56

Belge Tipi:

Makale

Yayın Tarihi:

6/2025

Belge Dili:

İngilizce

Document ID (Org No.):

2001351623

pISSN:

2147-7930