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

作者：许梦宇; 张安^*; 陈永; 陈光亭

来源：杭州电子科技大学学报(自然科学版), 2020, 40(05): 83-97.

DOI：10.13954/j.cnki.hdu.2020.05.015

• 顶点覆盖
• 正则图
• 割点
• 块图
• 最坏情况界

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

• 单位
  台州学院; 杭州电子科技大学