支配问题的研究进展

摘要

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