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（△为图中顶点的最大度数）。     

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

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

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

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

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

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

支配问题的研究进展

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

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

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

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

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

一种新的自组网极小连通支配集生成算法

自组网通过节点的自组织，构造成一种不需要任何基础设施的新型无线网络，基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足，基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS（Coloring Based—Minimum Connected Dominating Set）。CB-MCDS算法仅需要一跳邻居节点的拓扑信息，就能快速地构造出虚拟主干网，理论分析表明整个算法的时间和消息复杂度分别为O（A）和O（n△），该性能明显优于已有的算法.     

一种新的自组网极小连通支配集生成算法

自组网通过节点的自组织,构造成一种不需要任何基础设施的新型无线网络,基于连通支配集算法的虚拟主干网技术对于自组网的路由优化、能量保护和资源分配具有重要的作用。针对现有的连通支配集法存在的不足,基于图着色思想提出一种新的极小连通支配集构造算法CB-MCDS(Coloring Based-Minimum Connected Dominating Set)。CB-MCDS算法仅需要一跳邻居节点的拓扑信息,就能快速地构造出虚拟主干网,理论分析表明整个算法的时间和消息复杂度分别为O(△)和O(n△),该性能明显优于已有的算法。     

无线传感器网络中的连通支配集求解算法

连通支配集在无线传感器网络中有着重要的作用,通过对连通支配集的深入分析得到了关于连通支配集的一个新特性,即最小连通支配集是图的一棵包含最多叶子节点的生成树中的非叶子节点的集合。根据这个结论设计了一种全新的连通支配集求解算法,即通过建立一棵含叶子节点较多的生成树来寻找一个较小的连通支配集。仿真实验表明,新算法较前人的算法有明显的改进。     

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

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

一种求解最小连通支配集的高效近似算法

寻找出一个网络图的最小连通支配集有重要实际应用背景,然而如何找到它却是一个NP难题.本文设计了一种简单且高效的近似启发式算法构造网络图的连通支配集,该算法分为三个阶段:首先为顶点分配等级和生成顶点次序表,其次构造一个极大独立集,最后连接极大独立集中顶点.模拟实验表明该算法无论在运行时间和结果上都达到良好的效果.     

无线自组网络中的消息最优的连通控制集

在无线自组网中,提出了一种虚拟骨干网连通控制集(connected dominating set)。然而,寻找最小连通控制集(minimum connected dominating set)是一个NP困难的问题。在很多文献中已经提出了计算最小连通控制集的近似算法,这些算法大都存在近似比很差、时间复杂度和消息复杂度高等问题。近年来,提出了一些新的构造连通控制集的分布式启发式算法。这些新的启发式算法基于生成树的构造,这使得在迁移和拓扑更改的情况下维护连通控制集的通信开销非常昂贵,会对整个网络的性能及生存时间产生影响。因此消息最优的连通控制集也就被提出。在保证构建消息最优的连通控制集的情况下,通过建立一种新的求解极大独立集的模型,考虑到圆不能密铺会造成一定的误差,通过使用正六边形来代替R为0.5的圆,从而求得了一个更为精确的三跳内极大独立集,改善了文献[16]中的结果,得到了更小的连通控集近似比,其值为143opt+33。