顶点Pk覆盖问题的研究综述
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

国家自然科学基金(11471003,61425024)


A survey on vertex cover Pk problem
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    顶点覆盖问题是经典的NP完全问题,在排序、计算机网络等现实生活中有许多的应用.近几年来,许多研究者开始探究它的推广形式——顶点Pk覆盖(VCPk)问题,即寻找一个顶点子集,从拓扑结构图中删除后使得剩下的顶点导出的子图不包含Pk路,其中Pk是指包含k个顶点的路.本文简单介绍了VCPk问题的应用背景,归纳了它在近似算法、精确算法、参数化算法3个方面的主要研究进展,并分析了一些主要的方法和技巧.在此基础上,对VCPk问题及其相关问题的研究前景进行了展望.

    Abstract:

    Vertex cover problem is a classical NP complete problem,which has many applications in areas of sorting,computer network,etc.In recent years,many researchers begin to explore its generalized form,namely vertex cover Pk problem,which requires to find a subset of vertices such that the induced subgraphs by the rest vertices of the topological structure do not include any Pk path,where Pk is the path on k vertices.This paper firstly introduces the application background of vertex cover Pk problem,then summarizes current researches in approximation algorithms,exact algorithms and parameter algorithms,and analyzes some commonly used methods and techniques.On this basis,we point out the direction for further research on the vertex cover Pk problem and its related issues.

    参考文献
    相似文献
    引证文献
引用本文

王利民,华景煜.顶点Pk覆盖问题的研究综述[J].南京信息工程大学学报(自然科学版),2017,9(5):455-461
WANG Limin, HUA Jingyu. A survey on vertex cover Pk problem[J]. Journal of Nanjing University of Information Science & Technology, 2017,9(5):455-461

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2017-07-04
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2017-09-14
  • 出版日期:

地址:江苏省南京市宁六路219号    邮编:210044

联系电话:025-58731025    E-mail:nxdxb@nuist.edu.cn

南京信息工程大学学报 ® 2024 版权所有  技术支持:北京勤云科技发展有限公司