TREE-SEARCH ALGORITHMS FOR THE DOMINATING VERTEX SET PROBLEM

Let G = (V,E) be a directed graph. A subset S of V is said to be a dom inating set or externally stable set if it holds that, for every chi i s an element of V - S, there exists a node gamma is an element of S su ch that (chi,gamma)is an element of E. If in addition S does not conta in a dominating set, then S is said to be a minimal dominating set (MD S). The notion of MDS belongs to the family of covering problems and t herefore it has a wide range of applications, especially to network lo cation problems. In the literature the problem of generating the famil y of MDS and the corresponding NP-Hard problem of finding a minimum ca rdinality dominating set is solved in the framework of the general set covering problem. In this paper we face these problems using a graph algorithmic approach. Implicit enumeration tree search algorithms are developed and results of a computational experiment to graphs of vario us size are presented. The paper is completed with a numerical example .