Efficient Algorithm for Dominatig Set In Graph Theory Based on Fundamental Cut-Set

Year 2024, , 636 - 652, 01.06.2024

Furkan Öztemiz , Ali Karci

https://doi.org/10.35378/gujs.1243008

Abstract

Determining 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.

Keywords

Graph Theory, Dominating Set, Dominant Node, Karci Centrality, KMax Tree

References

• [1] Shen, C. and Li, T., “Multi-document summarization via the minimum dominating set”, In Proceedings of the 23rd International Conference on Computational Linguistics (COLING ’10), 984-992, (2010).
• [2] Fomin, F., Kratsch, V. D., Woeginger, G.J., “Exact (Exponential) Algorithms for the Dominating Set Problem”, Graph-Theoretic Concepts in Computer Science, 3353: 245–256, (2004).
• [3] Wang, N., Dai, J., Li D. and Li, M., “An approximation algorithm for connected dominating set in wireless ad hoc network”, (ICISCE 2012). 1–5, (2012).
• [4] Ruan, L., Du, H., Jia, X., Wu, W., Li, Y., Ko, K., “A greedy approximation for minimum connected dominating sets”, Theoretical Computer Science, 329(1-3): 325–330, (2004).
• [5] Xu, X., Tang, Z., Sun, W., Chen, X., Li, Y., Xia, G., Bi, X., Zong, Z., “An algorithm for the minimum dominating set problem based on a new energy function”, SICE 2004 Annual Conference, 924– 926, (2004).
• [6] Ho, K.C., Singh, Y. P., Ewe, H.T., “An Enhanced Ant Colony Optimization Metaheuristic for The Minimum Dominating Set Problem”, Applied Artificial Intelligence, 881–903, (2006).
• [7] Jovanovic, R., Tuba, M., “Ant Colony Optimization Algorithm with Pheromone Correction Strategy for the Minimum Connected Dominating Set Problem”, Computer Science and Information Systems, 10(1): 133–149, (2013).
• [8] Chalupa, D., “An order-based algorithm for minimum dominating set with application in graph mining”, Information Sciences, 426: 101–116, (2018).
• [9] Zhou, Y., Lv, G., Xiu, B., Zhang, W. and Cheng, Q., “A faster approximate method to identify minimum dominating set”, IEEE 5th International Conference on Software Engineering and Service Science, 443–448, (2014).
• [10] Grandoni, F., “A note on the complexity of minimum dominating set”, Journal of Discrete Algorithms, 4(2): 209–214, (2006).
• [11] Grinstead, D. L. and Slater, P. J., “On minimum dominating sets with minimum intersection”, Discrete Mathematics, 86(1-3): 239–254, (1990).
• [12] Campan, A., Truta, T.M., Beckerich, M., “Fast dominating set algorithms for social networks”, CEUR Workshop Proceedings, 1353, 55–62, (2015).
• [13] Guha, S., Khuller, S., “Approximation Algorithms for Connected Dominating Sets”, Algorithmica, 20: 374–387, (1998).
• [14] Chaoyi, P., Rui Z., Qing, Z., Junhu, W., “Dominating sets in directed graphs”, Information Sciences, 180(19): 3647-3652, (2010).
• [15] Yingshu, L., My, T., Thai, Feng, W., Chih-Wei, Y., Peng-Jun. W., Ding-Zhu, Du., “On greedy construction of connected dominating sets in wireless networks”, Wireless Communications And Mobile Computing, (5): 927–932, (2005).
• [16] Jwair, Z., Abdlhusein, M., “Some dominating results of the topological graph”, International Journal of Nonlinear Analysis and Applications, 1-9, (2022).
• [17] Purohit, G., N., Sharma, U., “Constructing Minimum Connected Dominating Set: Algorithmic approach”, International journal on applications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC), 2(3): 59-66, (2010).
• [18] Truta, T. M., Campan, A., Beckerich, M., “Efficient Approximation Algorithms for Minimum Dominating Sets in Social Networks”, International Journal of Service Science, Management, Engineering and Technology (IJSSMET), 9(2): 1–32, (2018).
• [19] Cao, H., Wu, W., Chen, Y., “A navigation route based minimum dominating set algorithm in VANETs”, International Conference on Smart Computing Workshops, 71–76, (2014).
• [20] Balasundaram, B., Butenko, S., “Graph Domination, Coloring and Cliques in Telecommunications”, Handbook of Optimization in Telecommunications, 865–890, (2006).
• [21] Shen, C. and Li, T., “Multi-document summarization via the minimum dominating set”, In Proceedings of the 23rd International Conference on Computational Linguistics, (COLING ’10), Association for Computational Linguistics USA, 984–992, (2010).
• [22] Öztemiz, F., Karcı, A., “Akademik Yazarların Yayınları Arasındaki İlişkinin Sosyal Ag Benzerlik Yöntemleri İle Tespit Edilmesi”, Uludag University Journal of The Faculty of Engineering, 25(1): 591–608, (2020).
• [23] Potluri, A., Singh, A., “Hybrid metaheuristic algorithms for minimum weight dominating set”, Applied Soft Computing, 13(1): 76–88, (2013).
• [24] Kapoor, K., Sharma, D., Srivastava, J., “Weighted node degree centrality for hypergraphs”, IEEE 2nd Network Science Workshop, 152–155, (2013).
• [25] Karci, A., “New Algorithms for Minimum Dominating Set in Any Graphs”, Anatolian Science, 5(2): 62–70, (2020).
• [26] [1]. Uehara, R., Toda, S., Nagoya, T., “Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs”, Discrete Applied Mathematics, 145(3): 479–482, (2005).
• [27] http://konect.cc/. Access date: 24.05.2023