4-正则图上的最小连通顶点覆盖问题

• 作者: 张安 许梦宇 陈光亭 陈永
• 来源期刊: 杭州电子科技大学学报（自然科学版）
• 关键词: 顶点覆盖 正则图 割点 块图 最坏情况界
• 年，卷（期）: 2020,（5）
• 页码范围: 83-87,97
• 页数: 6页
• 分类号: O221.7
• 语种: 中文
• DOI: 10.13954/j.cnki.hdu.2020.05.015

摘要

任给一个4-正则图,研究如何寻找4-正则图顶点数目最少的顶点覆盖问题,使其导出子图是一个连通图.已研究证明该问题是NP-难的且存在最坏情况界不超过4/3+O(1/n)的近似算法,其中n为4-正则图的顶点数.在此基础上,提出该算法的一个改进分析,使其最坏情况界中的O(1/n)项得以舍去.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈光亭		44	74	5.0	7.0
2	张安		24	15	2.0	2.0
3	陈永		22	14	2.0	2.0
4	许梦宇		1	0	0.0	0.0