基于搜索树的平面图支配集算法

许多来自工业应用的优化问题都是NP难问题。确定参数可解FPT作为处理这类问题的另外一种思路,在最近的10多年中受到了广泛的关注。支配集问题是图论中最重要的NP完全的组合优化问题之一,即使对于FPT体系而言,一般图中的支配集问题属于W2]完全的,意味着不可能设计出复杂度为f(k)no(1)的算法。在本文中,我们考虑在给定的平面图G=(V,E)中参数化支配集问题,给定参数k,看是否存在大小为k的顶点集合支配图中的其他顶点,当把问题限定在平面图上,这个问题属于确定参数可解。本文给出了基于两组归约规则的搜索树算法,通过使用规约技术化简实例,构造搜索树,得到了复杂度为O(8kn)的算法,同时通过相关实验结果显示了归约规则对算法的作用。

A Refined Algorithm for the Dominating Sets on Planar Graphs Based on Search Trees

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 W2]-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.