A Rough-Set Based Solution of the Total Domination Problem

摘要

This paper aims to provide a rough set-based reduction solution for a type of domination problem in graph theory. First, we introduce a decision table to represent the vertices and edges of a graph. Second, we claim that computing a minimal total dominating set of a graph is equivalent to finding a reduct of the induced decision table. Then, a reduction algorithm in rough set theory is designed for finding a suboptimal total dominating set of a graph. In the end, numerical experiments are conducted to examine the effectiveness and efficiency of the proposed algorithm.