OTIS网络的支配集问题算法研究

图的最小支配集问题和最小连通支配集问题在网络与并行分布式计算中有重要应用,计算上它们都属于NP难问题。OTIS网络是一类可以任意图为因子网络的复合网络,它能继承因子网络的良好特性,因而成为可扩展性、模块化、容错性的大规模并行计算机系统的体系结构形式之一。研究如何构建OTIS网络的较小支配集和连通支配集。基于OTIS网络构图规则,分别根据因子网络的支配集算法和连通支配集算法得到了求解OTIS网络的支配集算法和连通支配集算法。从理论上分析了这些算法的性能,并通过实例进行了验证。     

一种高效的最小连通支配集贪心算法

连通支配集（CDS）在无线网络设计中有着广泛应用,现有多数连通支配集算法每次处理一个节点。提出了一个同时处理多个节点的贪心算法（GCDS）,依次选取最小度数节点以及该节点两跳内的一至两个节点为处理节点,当删除处理节点后剩余点不连通时减少处理的节点数,进而把节点分为支配点和受支配点;最终所有支配点构成一个近似最小连通支配集。在模拟无线传感器网络的单位圆盘图上的仿真结果表明,GCDS算法具有较低的时间复杂度,所得到的连通支配集大小优于已有算法。     

无向图中连通支配集问题的精确算法

图◢G=（V,E）的一个支配集DV是一个顶点子集,使得图中每一个顶点要么在D中,要么至少与D中的一个顶点相连。连通支配集问题是找到一个顶点数最小的支配集S,并且S的导出子图G［S］是连通图。◣该问题是一个经典的NP难问题,可应用于连通设施选址、自适应网络等领域。针对无向图中连通支配集问题,仔细分析该问题的图结构性质,挖掘出若干有效的约简规则和分支规则,设计了一个分支搜索算法,并采用了测量治之方法分析算法的运行时间,最终得到了一个运行时间复杂◢度为O*△（1.93n△）的精确◣算法。     

测试集问题的集合覆盖贪心算法的深入近似

测试集问题是一个有着广泛应用的NP难问题.集合覆盖贪心算法是测试集问题的一个常用近似算法,其由集合覆盖问题得到的近似比21nn+1能否改进是一个公开的问题.集合覆盖贪心算法的推广被用来求解生物信息学中出现的冗余测试集问题.通过分析条目对被区分次数的分布情况,用去随机方法证明了集合覆盖贪心算法对测试集问题的近似比可以为1.51nn+0.5lnlnn+2,从而缩小了这种算法近似比分析的间隙.另外,给出了集合覆盖贪心算法对冗余度为n-1的加权冗余测试集问题的近似比的紧密下界(2-o(1))lnn-Θ 1).     

带测度函数的连通支配集问题

连通支配集问题在网络广播上有着广泛的应用,本文引入测度函数的概念,提出了带测度函数的连通支配集问题（CDS（F））,使得它具有更广的应用范围。文中首先给出问题的形式定义,证明了它在各种情形下的NP完全性,并给出多项式时间的近似算法,它的近似度为Ln△＋3（△为图中顶点的最大度数）。     

自组织网络分布式最小连通支配集创建算法*

针对无线自组织分组（Ad hoc）网络中最小连通支配集（MCDS）创建NP难问题,提出了一种分布式的最小连通集创建算法DMCA。DMCA基于最大独立集（MIS）的构建,只需要周围一跳邻居的信息,在不超过三跳距离的一对支配节点之间找出一条最短路径。对DMCA算法的性能分析表明,DMCA具有常数的近似比、线性的时间和消息复杂度。详细的仿真实验以及与其他创建最小连通支配集算法的比较表明,提出的DMCA算法在节点数量与节点传输范围变化时创建的最小连通集更小。     

无线传感器网络极小连通支配集算法的改进

无线传感器网络中,基于极小连通支配集的虚拟骨干网的构建使得路由搜索空间集中在支配节点之间,能够有效节省网络资源,减少冗余转发节点.首先提出连通支配集的数学模型.基于WL算法,提出改进的极小连通支配集分布式算法.仿真结果表明,改进算法求得的连通支配集较小,可为无线传感器网络中的路由协议提供通讯基础.     

传感器网络中高效的最小连通支配集求解算法

在无线传感器网络中,连通支配集被广泛应用于构建虚拟主干。由于求解最小连通支配集是一个NP难问题,许多近似算法被提出用于构建可用的最小连通支配集。针对当前近似算法存在的不足,我们提出了一个新的分布式近似构造算法—CDS-HG,该算法用层次图对无线传感器网络进行建模,算法用基于竞争的贪心策略从每一层选出最少的节点去支配下一层的所有节点。理论分析和模拟结果表明,CDS-HG算法产生的连通支配集是目前最小,并且其消息复杂度也是目前最低的。     

支配问题的研究进展

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

最小连通支配集问题的化简算法

分析连通支配集的支配性约束和连通性约束条件,提出2条针对简单无向连通图最小连通支配集问题的化简规则.规则通过对图中节点的邻节点进行分类以及寻找图的割点提前确定一些必选节点,同时删除一些多余节点,从而降低原问题的规模.从理论上证明了化简规则的正确性,并通过随机仿真实验验证化简规则的有效性.     

链路约束的分布式网络监测模型

分布式网络监测系统能够实时有效地收集网络性能数据,但收集过程受到链路延迟和路由跳数的约束．链路约束的分布式网络监测模型研究如何在链路约束下用最小的代价部署整个分布式网络监测系统;链路约束的演化网络监测模型研究在网络演化的情况下,如何用最小的更新代价重新部署监测系统使之满足链路约束．求取这两个模型的最优解的问题都是NP难的．通过指定权函数的形式,两个模型对应的最优化问题能够映射成带权的集合覆盖问题,采用贪婪策略能够得到近似比不超过ln n＋1的近似算法,其中n是被监测节点的数目．通过仿真实验还讨论了如何选择恰当的链路延迟约束值．     

图的支配集若干问题的研究

本文提出了两个图支配集问题的变形即C强支配集和完全支配集问题,这两个问题都有重要的实际应用背景。我们证明了它们的判定问题是NP完全的,并且给出了它们相应优化问题的近似算法以及算法的近似度分析。     

基于规则综合质量的属性值约简算法

属性值约简是粗集理论的核心内容之一.将属性值约简和数据挖掘相结合,给出支持度、置信度、覆盖度的定义.在此基础上,提出了一种新的属性值约简算法一基于规则综合质量的属性值约简算法.通过算法复杂度分析说明,该算法在一定程度上解决了属性值约简的NP难问题.实例仿真表明该算法在解决一些相关实际问题方面是可行的,具有一定的实用价值.     

一种改进的无线传感器网络EEMCDS算法

针对无线传感器网络中的有效路由,提出了一种改进的,基于最小连通支配集的能量有效算法IEEMCDS(Improved Energy-Efficient Minimum Connected Dominating Set).路由搜索主要集中在连通支配集内,通信量小.该算法是一个能量有效的分布式算法,在维护最小连通支配集时,充分考虑了节点的能量问题,优先选择高能量的节点充当连通支配集节点,提出了支配节点能量最小阈值调整法,可以有效地延长网络寿命.实例仿真表明在改进算法的连通支配集中,高能量的节点在支配集中一直占有较高的比例,从而有效地延长了网络寿命.     

能量有效的最小连通支配集近似算法

针对无线自组传感器网络中有效路由提出的一种能量有效的最小连通支配集近似算法EEMCDS(Energy-Efficient minimum connected dominating set),路由搜索主要集中在连通支配集内.本文提出一个能量有效的简洁有效的分布式算法,该算法根据各节点所具有的能量不同,优先选择高能量的节点作为连通支配集节点,可以有效地延长网络寿命.实例仿真表明在连通支配集节点数量较少的情况下,高能量的节点在支配集中所占的比例也是较高的.     

控制集与部分控制集问题的原始-对偶算法

图的控制集问题是一类应用广泛的组合最优化问题。本文利用控制集和部分控制集问题的整数规划模型和原始-对偶方法,分别给出这两个问题近似度为△＋1的近似算法（△为图中顶点最大度）。     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。