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

On the Vertex Cover P3 Problem in Cubic Graphs

作　　者：张雷 张安[1] 陈永[1] 陈光亭[1] ZHANG Lei;ZHANG An;CHEN Yong;CHEN Guangting(School of Science,Hangzhou Dianzi University.,Hangzhou Zhejiang 310018,China)

机构地区：[1]杭州电子科技大学理学院

出　　处：《杭州电子科技大学学报（自然科学版）》2019年第5期94-97,共4页Journal of Hangzhou Dianzi University：Natural Sciences

基　　金：国家自然科学基金资助项目(11571252,11771114);浙江省自然科学基金资助项目(LY16A010015)

摘　　要：研究了三正则图上的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.)

关 键 词：三正则图 P 3顶点覆盖 近似算法 最坏情况分析 

分 类 号：O221.7[理学—运筹学与控制论]