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

论文摘要

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

论文目录

• 0 引 言
• 1 预备知识
• 2 近似算法
• 3 结束语

文章来源

类型: 期刊论文

作者: 张雷,张安,陈永,陈光亭

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

来源: 杭州电子科技大学学报(自然科学版) 2019年05期

年度: 2019

分类: 信息科技,基础科学

专业: 数学

单位: 杭州电子科技大学理学院

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

分类号: O157.5

DOI: 10.13954/j.cnki.hdu.2019.05.017

页码: 94-97

总页数: 4

文件大小: 330K

下载量: 24