New Algorithms for Minimum Dominating Set in Any Graphs
Ali Karcı · DergiPark (Istanbul University) · 2020
It is known that there are many NP-hard and NP-complete problems in graph theory.The aim of this paper is to propose some basic methods for solving problem of obtaining minimum dominating set which is one of these problems.In order to construct such fundamentals, a special spanning tree for given graph (except trees) was obtained by using proposed method, and it was called as Kmax tree.The fundamental cut-sets of given graph were obtained by using this spanning tree.The dominance of each node in the given graph were computed with respect to these fundamental cut-sets, node degrees in graph and corresponding Kmax tree for the first time in this paper.The dominance of each node illustrates whether that node will take place in minimum dominating set or not.For the sake of obtaining the minimum dominating set, there are three algorithms (proposed in this study for the first time) which are used in sequential order.Application of these algorithm concludes in obtaining the minimum dominating set which is an NP-hard and NP-complete problem.The proposed method in this study verified that this problem can be solved with these deterministic algorithms.