论文部分内容阅读
最优顶点覆盖问题是6个基本的NP完全问题之一,无法在多项式时间内得到最优解,除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时,证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。
改进的最优顶点覆盖贪心边近似算法
【摘 要】
：
最优顶点覆盖问题是6个基本的NP完全问题之一,无法在多项式时间内得到最优解,除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时,证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。
【机 构】
：
康定民族师范高等专科学校计算机科学系
【出 处】
：
计算机应用
【发表日期】
：
2006年01期
其他文献
分析了P2P匿名通信系统模型及攻击模型,基于信息熵,针对共谋攻击,度量了几种典型的P2P匿名系统的接收者匿名度,分析了系统匿名性与系统规模N、恶意节点比例、路径长度及转发概率的关系。计算数据表明,嵌套加密使系统获得强匿名,接收者的匿名度随系统规模等的增大而增大,随恶意节点比例的增大而减小,受恶意节点比例及系统规模影响较大,受路径长度影响较小。
改变荫罩式等离子显示板(SM-PDP)的驱动电压波形,会使PDP在放电过程中的空间电场发生变化,从而使放电过程、放电特性发生变化.根据PDP放电特点,选择一个合适的驱动波形,可以
金刚石由于其低的介电常数、高的导热率和优良的机械性能,将其应用于微波管改善其散热性能取代传统有毒的氧化铍陶瓷,是微波管螺旋线优良的支撑材料.本文首次采用等离子体化
2000年7月，金毅接过了天津第一机床总厂厂长和党委书记的重担。那时，说他是临危受命一点也不为过。这家曾拥有近5000名职工、号称中国机床行业“十八罗汉”之一的国家大型骨干