Tree search algorithms for the dominating vertex set problem

Abstract

Let G = (V E) be a directed graph. A subset S of V is said to be a dominating set or externally stable set if it holds that, for every x∊ V − S, there exists a node y ∊ S such that (x y) ∊ E. If in addition S does not contain a dominating set, then S is said to be a minimal dominating set (MDS).

The notion of MDS belongs to the family of covering problems and therefore it has a wide range of applications, especially to network location problems. In the literature the problem of generating the family of MDS and the corresponding NP-Hard problem of finding a minimum cardinality 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 various size are presented.

The paper is completed with a numerical example.

Keywords:

• Dominating set
• externally stable set
• branch
• backtrack
• tree search
• implicit enumeration

C.R.Categories:

• G.2.2