Malatya Hakim Küme Algoritmasının Analitik Doğrulaması: Artık Düğümler Olmadan Optimal Hakim Kümelerin Oluşturulması

Year 2025, Volume: 13 Issue: 1, 46 - 56, 30.06.2025

Şeyda Karcı , Fatih Okumuş

https://doi.org/10.18586/msufbd.1643589

Abstract

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, MDSA'nı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, MDSA'nı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 MDSA'nı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.

Keywords

Hâkim Kümeler , Malatya Merkeziyet Değeri , Malatya Hâkim Küme Algoritması , Açgözlü Algoritmalar , Dinamik Programlama , Teorik İspat

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

Abstract

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.

Keywords

Dominating Sets , Malatya Centrality Value , Malatya Dominating Set Algorithm , Greedy Algorithms , Dynamic Programming , Theoretical Proof

References

• [1] A. Mitra and S. Paul, “Analyzing social networks with dynamic graphs: Unravelling the ever-evolving connections,” Appl. Graph Data Sci., pp. 195–214, Jan. 2025, doi: 10.1016/B978-0-443-29654-3.00020-X.
• [2] L. Yu, Z. Wang, Y. Liu, and Z. Yang, “Sampled-Data-Based Privacy-Preserving Scaled Consensus for Nonlinear Multiagent Systems: A Paillier Encryption Approach,” IEEE Trans. Syst. Man, Cybern. Syst., 2024, doi: 10.1109/TSMC.2024.3517473.
• [3] R. Das and M. Soylu, “A key review on graph data science: The power of graphs in scientific studies,” Chemom. Intell. Lab. Syst., vol. 240, p. 104896, Sep. 2023, doi: 10.1016/J.CHEMOLAB.2023.104896.
• [4] L. D. F. Costa et al., “Analyzing and modeling real-world phenomena with complex networks: a survey of applications,” Adv. Phys., vol. 60, no. 3, pp. 329–412, May 2011, doi: 10.1080/00018732.2011.572452.
• [5] E. Gayathiri et al., “Computational approaches for modeling and structural design of biological systems: A comprehensive review,” Prog. Biophys. Mol. Biol., vol. 185, pp. 17–32, Dec. 2023, doi: 10.1016/J.PBIOMOLBIO.2023.08.002.
• [6] S. S. Singh, S. Muhuri, S. Mishra, D. Srivastava, H. K. Shakya, and N. Kumar, “Social Network Analysis: A Survey on Process, Tools, and Application,” ACM Comput. Surv., vol. 56, no. 8, Apr. 2024, doi: 10.1145/3648470.
• [7] D. Karthika, R. Muthucumaraswamy, M. Bentert, S. Bhyravarapu, S. Saurabh, and S. Seetharaman, “On the Complexity of Minimum Membership Dominating Set,” pp. 94–107, 2025, doi: 10.1007/978-3-031-82670-2_8.
• [8] M. Shahraeini, G. Kohsari, and M. H. Javidi, “Comparison of Meta-Heuristic Algorithms for Solving Dominating Set Problems in WAMS Design,” Proc. - 2022 8th Int. Iran. Conf. Signal Process. Intell. Syst. ICSPIS 2022, 2022, doi: 10.1109/ICSPIS56952.2022.10044037.
• [9] D. L. L. Moura, A. L. L. Aquino, and A. A. F. Loureiro, “Towards data VSN offloading in VANETs integrated into the cellular network,” MSWiM 2019 - Proc. 22nd Int. ACM Conf. Model. Anal. Simul. Wirel. Mob. Syst., pp. 235–239, Nov. 2019, doi: 10.1145/3345768.3355937.
• [10] M. M. Daliri Khomami, A. Rezvanian, N. Bagherpour, and M. R. Meybodi, “Minimum positive influence dominating set and its application in influence maximization: a learning automata approach,” Appl. Intell., vol. 48, no. 3, pp. 570–593, Mar. 2018, doi: 10.1007/S10489-017-0987-Z/FIGURES/7.
• [11] R. Sun, J. Wu, C. Jin, Y. Wang, W. Zhou, and M. Yin, “An efficient local search algorithm for minimum positive influence dominating set problem,” Comput. Oper. Res., vol. 154, p. 106197, Jun. 2023, doi: 10.1016/J.COR.2023.106197.
• [12] M. A. Akbay, A. López Serrano, and C. Blum, “A Self-Adaptive Variant of CMSA: Application to the Minimum Positive Influence Dominating Set Problem,” Int. J. Comput. Intell. Syst., vol. 15, no. 1, pp. 1–13, Dec. 2022, doi: 10.1007/S44196-022-00098-1/TABLES/4.
• [13] J. Raczek and M. Miotk, “Two Approaches to Constructing Certified Dominating Sets in Social Networks,” IEEE Access, 2025, doi: 10.1109/ACCESS.2025.3532392.
• [14] S. Wuchty, “Controllability in protein interaction networks,” Proc. Natl. Acad. Sci. U. S. A., vol. 111, no. 19, pp. 7156–7160, May 2014, doi: 10.1073/PNAS.1311231111/SUPPL_FILE/PNAS.201311231SI.PDF.
• [15] S. K. Grady, K. A. Peterson, S. A. Murray, E. J. Baker, M. A. Langston, and E. J. Chesler, “A graph theoretical approach to experimental prioritization in genome-scale investigations,” Mamm. Genome, vol. 35, no. 4, pp. 724–733, Dec. 2024, doi: 10.1007/S00335-024-10066-Z/FIGURES/7.
• [16] Y. Tokuhara, T. Akutsu, J. M. Schwartz, and J. C. Nacher, “A practically efficient algorithm for identifying critical control proteins in directed probabilistic biological networks,” npj Syst. Biol. Appl. 2024 101, vol. 10, no. 1, pp. 1–12, Aug. 2024, doi: 10.1038/s41540-024-00411-y.
• [17] J. M. Etancelin, A. Fabbri, F. Guinand, and M. Rosalie, “DACYCLEM: A decentralized algorithm for maximizing coverage and lifetime in a mobile wireless sensor network,” Ad Hoc Networks, vol. 87, pp. 174–187, May 2019, doi: 10.1016/J.ADHOC.2018.12.008.
• [18] N. R. Sivakumar, S. M. Nagarajan, G. G. Devarajan, L. Pullagura, and R. P. Mahapatra, “Enhancing network lifespan in wireless sensor networks using deep learning based Graph Neural Network,” Phys. Commun., vol. 59, p. 102076, Aug. 2023, doi: 10.1016/J.PHYCOM.2023.102076.
• [19] Y. Sabri and A. Hilmani, “An IoT-Based 5G Wireless Sensor Network Employs a Secure Routing Methodology Leveraging DCNN Processing,” Trans. Emerg. Telecommun. Technol., vol. 35, no. 12, p. e70025, Dec. 2024, doi: 10.1002/ett.70025.
• [20] S. Saurabh, S. Madria, A. Mondal, A. S. Sairam, and S. Mishra, “An analytical model for information gathering and propagation in social networks using random graphs,” Data Knowl. Eng., vol. 129, p. 101852, Sep. 2020, doi: 10.1016/J.DATAK.2020.101852.
• [21] F. Okumuş and Ş. Karcı, “MDSA: A Dynamic and Greedy Approach to Solve the Minimum Dominating Set Problem,” Appl. Sci. 2024, Vol. 14, Page 9251, vol. 14, no. 20, p. 9251, Oct. 2024, doi: 10.3390/APP14209251.
• [22] A. Science, S. Yakut, F. Öztemiz, and A. Karcı, “A New Approach Based on Centrality Value in Solving the Maximum Independent Set Problem: Malatya Centrality Algorithm,” Comput. Sci., vol. Vol:8, no. Issue:1, pp. 16–23, Jun. 2023, doi: 10.53070/BBD.1224520.
• [23] A. Science and F. Öztemiz, “İki Parçalı Eşleştirme ile Maksimum Akış,” Bilgi. Bilim., vol. Vol:8, no. Issue:2, pp. 102–109, Dec. 2023, doi: 10.53070/BBD.1386446.
• [24] H. Jiang and Z. Zheng, “An Exact Algorithm for the Minimum Dominating Set Problem,” 2023.