论文部分内容阅读
复杂性理论中，支配问题是一类重要的问题，被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集（vDS）问题和边支配集（EDS）问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析，并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的（FPT）。利用树分解和分支搜索等技术，人们分别对平面图VDS问题和一般图EDS问题提出了一系