期刊文章详细信息
改进的最优顶点覆盖贪心边近似算法
Improved greedy-edge approximation algorithm of the optimal vertex-cover
文献类型：期刊文章
机构地区：[1]康定民族师范高等专科学校计算机科学系,四川康定626001
年 份：2006
卷 号：26
期 号：1
起止页码：149-151
语 种：中文
收录情况：AJ、BDHX、BDHX2004、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、ZMATH、核心刊
摘 要：最优顶点覆盖问题是6个基本的NP完全问题之一,无法在多项式时间内得到最优解,除非P=NP。文中给出改进的最优顶点覆盖贪心边近似算法的同时,证明并讨论了它的近似因子是一个不大于2的与单点贪心边数和双点贪心边数相关的因子。
关 键 词：顶点覆盖 近似算法 近似因子 单点贪心边 双点贪心边 贪心边
分 类 号：TP751] TP301.6]
参考文献：
正在载入数据...
二级参考文献：
正在载入数据...
耦合文献：
正在载入数据...
引证文献：
正在载入数据...
二级引证文献：
正在载入数据...
同被引文献：
正在载入数据...
