Approximate Algorithm Of Minimum Dominating Set For Undirected Graph Based On Rough Set

Dominating set of graphs and its extension are classical combinatorial optimization problems in graph theory,which have been widely used in optimization theory,urban traffic route planning,communication and other fields.However,the minimum dominating set and its extension problem have been proved to be NP-hard problem,and the complexity and accuracy of the existing approximate solution algorithms need to be further improved.In this paper,based on the rough set theory,the method for solving the minimum dominating set of undirected graphs is investigated,and the main work and innovation points are as follows:1.Based on the idea of attribute order in rough set theory,an algorithm for solving the minimal dominant set of undirected graphs under vertex order is proposed.First,a fully ordered relation(ie vertex order)is defined on the vertex set of a given undirected graph,and then a binary equivalent relation is defined on the vertex closed adjacency set.secondly,based on the binary equivalence relation,a minimal dominant set algorithm under vertex order is proposed.Finally,the completeness and uniqueness of the algorithm for solving the minimal dominant set under a given vertex order are proved,and the correctness and effectiveness of the algorithm are verified by an example.2.Based on the attribute reduction principle of decision table in rough set theory,a heuristic minimum dominant-set approximation algorithm for undirected graphs is proposed.Firstly,an induced decision table is constructed by using the adjacency matrix of graphs,and it is proved that the minimum dominant set of graphs is equivalent to the minimum attribute reduction of the induced decision table.Secondly,based on the characteristics of the induced decision table,a heuristic minimal dominant set approximation algorithm with lower complexity is proposed by using the forward and backward search mechanism and the cumulative accumulation strategy of the induced decision table positive domain.Finally,the experimental comparison of the proposed algorithm with the typical algorithm on the common data set shows that the proposed algorithm has obvious advantages in terms of running time and can obtain the approximate minimum dominant set with higher accuracy.3.An incremental dominant set updating algorithm is proposed for dynamic graphs.Firstly,the characteristics of the dominant set under four basic dynamic changes of undirected graphs(adding vertices,deleting vertices,adding edges and deleting edges)are analyzed,and the corresponding updating strategies of the dominant set are given.Then,an incremental updating algorithm of minimal dominant set is proposed for dynamic graphs.Finally,the correctness and effectiveness of the incremental update algorithm are verified by experimental comparison with the non-incremental update algorithm on the public data set.In conclusion,some progress has been made in the approximate solution algorithm of the minimum dominant set for undirected graphs in this paper,which is helpful for the further study of the minimum dominant set and its extension,and is expected to promote new ideas in the study of rough set theory and graph theory.