I. Introduction
Co mparing the governing sets of graphs and the attribute reduction method of decision tables, it is not difficult to find that they can be obtained by constructing Boolean functions for logical operations, which shows that it is possible to study related problems in graph theory based on rough set theory. A rough set solution method for some related problems in graph theory is proposed [1]–[4]. This paper uses the adjacency matrix to cons truct the induced decis ion tab le for undirected graph, and proposes a heuristic minimum dominating set approximation algorithm based on rough set theory [5], [6]. The algorithm uses forward and backward search mechanism, not only can obtain the minimal dominating set of the graph, but also can obtain a better approximate minimal dominating set.