摘要
研究了三正则图上的P3顶点覆盖问题。P3顶点覆盖问题是指删除原图中的若干顶点使得剩余子图中不存在长度大于等于3的路径,目标是删除点的个数尽可能少。通过分析贪婪算法解的结构,证明了算法的近似比为3/2,并给出了紧例。
In this paper,we study the P3 vertex cover problem on three regular graphs.The problem of P3 vertex cover is that after removing some points in the original graph,the remaining graph does not have a path with a length greater than 3,and our goal is to minimize the total number of removed points.(By analyzing the structure of the greedy algorithm,and the new approximation ratio is 3/2,and a tight example is given.)
作者
张雷
张安
陈永
陈光亭
ZHANG Lei;ZHANG An;CHEN Yong;CHEN Guangting(School of Science,Hangzhou Dianzi University.,Hangzhou Zhejiang 310018,China)
出处
《杭州电子科技大学学报（自然科学版）》
2019年第5期94-97,共4页
Journal of Hangzhou Dianzi University：Natural Sciences
基金
国家自然科学基金资助项目(11571252,11771114)
浙江省自然科学基金资助项目(LY16A010015)
关键词
三正则图
P
3顶点覆盖
近似算法
最坏情况分析
cubic graph
vertex cover P 3 problem
approximation algorithm
worst-case analysis
