三正则图上的P3顶点覆盖问题

• 作者: 张安 张雷 陈光亭 陈永
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 三正则图 P3顶点覆盖 近似算法 最坏情况分析
• 年，卷（期）: 2019,（5）
• 页码范围: 94-97
• 页数: 4页
• 分类号: O221.7
• 语种: 中文
• DOI: 10.13954/j.cnki.hdu.2019.05.017

摘要

研究了三正则图上的P3顶点覆盖问题.P3顶点覆盖问题是指删除原图中的若干顶点使得剩余子图中不存在长度大于等于3的路径,目标是删除点的个数尽可能少.通过分析贪婪算法解的结构,证明了算法的近似比为32,并给出了紧例.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈光亭	杭州电子科技大学理学院	44	74	5.0	7.0
2	张安	杭州电子科技大学理学院	24	15	2.0	2.0
3	陈永	杭州电子科技大学理学院	22	14	2.0	2.0
4	张雷	杭州电子科技大学理学院	4	2	1.0	1.0