无线网络中一种简单的弱连通支配集构造策略

通过构造边支配集,提出了求解无线网络中弱连通支配集的集中式构造算法,该算法的时间复杂度为O(|N|+|E|)。同时在保证支配集的支配性和弱连通性不变的情况下,给出了两种修剪策略,以减小所求弱连通支配集的规模。从理论上证明了本算法的正确性,并通过仿真验证了算法的有效性。与已有结果相比,该算法可以产生规模更小的弱连通支配集。

支配问题的研究进展

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