顶点覆盖问题的贪心算法的设计与分析

• 作者: 姚朝灼
• 来源期刊: 福州大学学报(自然科学版)
• 学科: 工学
• 关键词: 顶点覆盖 贪心算法 NP—困难
• 年，卷（期）: 2001,（1）
• 页码范围: 8-11
• 页数: 4页
• 分类号: TP301.6
• 字数: 1965字
• 语种: 中文
• DOI: 10.3969/j.issn.1000-2243.2001.01.003

摘要

设计了解顶点覆盖问题的贪心算法，并证明其相对比率η≤H(d)，d为图中最大的顶点度数，H(d)=∑1/j(j=1，2，……，d).当d≤3时，解的精确度有明显改善.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姚朝灼	福州大学计算机科学与技术系	10	40	4.0	6.0