关键词: 算法, 搜索树, 支配集, 确定参数可解

Abstract:

The dominating set in graphs is considered to be among the most important problems in combinatorial optimization, which is NPcomplete. From the viewpoint of FixedParameter Tractable, the problem is known to be W［2］complete for general graphs, which means that it is impossible to design an algorithms solve the problem with running time f(k)no(1).We investigate the version where we are given a planar graph G=(V ,E), a parameter k, and ask for a set of vertices of size at most k that dominate all other vertices. It is known to be fixedparameter tractable when restricted to a planar graph. We also give a search tree algorithm based on the two sets of reduction rules and the experiments to show the efficiency between different sets of reduction rules.

Key words: algorithm;search tree;dominating set;fixedparameter tractable