支配问题的研究进展

Algorithms for Dominating Problems:A Survey

复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。

In complexity theory, dominating problem is an important problem, which has important applications in many fields such as resource allocations, electric networks and wireless ad hoc networks. The two most known dominating problems are Vertex Dominating Set（VDS） and Edge Dominating Set（EDS） problem. People designed and analyzed exa- ct algorithms for the two problems by dynamic programming and measure-and-conquer techniques and proposed many approximation algorithms for EDS problem by reducing the problem to Edge Cover problem. Recently, parameterized dominating problem has attached considerable attention. Planar VDS and General EDS problem has been proved to be Fixed-Parameter Tractable（FPT） problem, and many techniques such as tree decomposition and branch-search have been used in the design of FPT algorithms for them. The paper presented the classification for the two problems respec tively, and gave definitions and some relative algorithms for each derivative problem. Furthermore, the Matrix Domina- ting Set problem and some research directions on dominating problem were also introduced.