作者:赵燕萍 期刊:《山西师范大学学报·自然科学版》 2012年第04期
本文提出了基于图论算法的关键蛋白质识别方法,选择合理的候选关键蛋白质集合和相关的路径参数,对大规模蛋白质互作用网络的关键蛋白质进行预测.实验表明,该算法是有效的.
11月11日晚8时北京2008年奥运会开始1000天倒计时,北京奥运会吉祥物也在万众期待中揭晓——吉祥物由5个拟人化的娃娃形象组成,统称“福娃”。一夜之间,五个吉祥物就掀起全国上下普遍赞赏的热潮。这五个可爱奥运吉祥物“福娃”,分别以“鱼、熊猫、奥运圣火、藏羚羊及京燕”为主题,并依据“北京欢迎你”五个字,将它们命名为“贝贝、晶晶、欢欢、迎迎,妮妮”。
近日,北京市经济和信息化局印发《北京市5G产业发展行动方案(2019年-2022年)》(以下简称《方案》)。根据该方案,北京将集中优势力量在5G关键元器件等技术薄弱环节补齐短板,在行业应用方面率先形成应用案例,加快网络建设并在全国率先实现5G热点覆盖。
作者:张佳男; 肖鸣宇 期刊:《计算机科学》 2018年第04期
图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行...
作者:肖鸣宇; 陈建二; 韩旭里 期刊:《计算机学报》 2005年第02期
给出了一种提高低度图点覆盖和独立集问题下界的精确算法.通过分析如何有效地减少图中的顶点来打破原问题的NP-Hard结构建立起搜索递推关系;得出3度图的最小点覆盖问题的解决时间为O(1.1033n),参数化的3度图点覆盖问题的解决时间为O(kn+1.2174k);将此算法应用到3度图的最大独立集问题上,可以得到运行时间为O(1.1033n)的解.以上3结果均打破原有最佳下界.
作者:王行甫; 苗付友; 熊焰; 周大铨; 岳丽华 期刊:《电子学报》 2006年第B12期
在无线传感器网络(Wireless Sensor Network)中,随着能量的消耗将导致部分节点失去工作效能,无法保证预先部署的节点有效地覆盖被监测区域或目标.因此,本文提出一种基于蒙特卡罗(MC)算法的目标点覆盖质量评估技术,该技术每次从目标点集合中任意选取若干点进行检测,若全部满足覆盖质量要求则返回,否则标定不满足条件的目标点.反复使用该技术有限次,可以使覆盖质量评估的正确率超过99%,从而可以有效解决无线传感器网...
作者:常乐; 王建新; 陈建二 期刊:《计算机科学》 2007年第10期
皇冠分解和NT算法长久以来被认V1为是在参数化点覆盖的求核问题中有着广泛应用的两种相互独立的方法。NT算法将给定的图分成V2,V1和V1/2三部分,将砜和V1移除从而完成图的分解。而皇冠分解则是找到尽可能多的皇冠结构,删除这些皇冠以降低图规模。最近的研究结果表明NT算法和皇冠分解存在很强的内在联系:NT算法中的砜,V1部分正好构成一个皇冠结构。本文进一步研究了皇冠分解和NT算法的内在联系,提出了严格皇冠和非严格皇冠的...
作者:吴春 朱国魂 谢玉忠 林宏 期刊:《计算机系统应用》 2010年第09期
最小顶点覆盖问题是图论中经典的组合优化问题,在实际生活中有着广泛的应用价值。根据最小顶点覆盖与最大独立集在图论中事实上是属于等价问题这一特性,从最大独立集的角度出发,根据最大独立集的特性,设计了一种求解简单平面图的最大独立集算法,从而求出最小顶点覆盖。通过实验结果的比对验证算法的正确性和有效性。
作者:黄海滨 杨路明 王建新 李绍华 期刊:《计算机工程与应用》 2008年第27期
针对已有方法对关键蛋白识别度不高的现状,认为进一步提高识别度有两条途径:一是发现与关键蛋白关系更密切的参数,二是充分挖掘现有参数的信息并进行有效地整合。由于点覆盖在网络(图)拓扑结构上的重要地位而研究将其引入关键蛋白质的识别中:针对算法的复杂性引进参数计算的相关算法将复杂度大幅度降低的同时对蛋白质网络进行最小点覆盖分析并获得一种新的拓扑参数-点覆盖参数,相关分析表明该参数与关键蛋白有着密切的联系。进...
作者:黄海滨 杨路明 王建新 陈建二 李绍华 期刊:《计算机研究与发展》 2009年第01期
点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形子图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论:2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对...
作者:焦丽 唐恒永 期刊:《运筹与管理》 2009年第03期
本文讨论了瓶颈型Hamming距离下约束最小支撑树的反问题,通过修改给定网络边上的权,使得修改后网络中指定的支撑树是最小支撑树并且支撑树中的最大边的权不超过给定的常数,用瓶颈型Hamming距离来衡量修改的费用,且修改费用最小。把瓶颈型Hatnming距离下约束最小支撑树的反问题转化为最小瓶颈权点覆盖问题,并给出了多项式算法。