南京信息工程大学学报2017，Vol.9Issue(5)：455-461,7.DOI:10.13878/j.cnki.jnuist.2017.05.001
顶点Pk覆盖问题的研究综述
A survey on vertex cover Pk problem
摘要
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覆盖/近似算法/精确算法/参数化算法Key words
vertex cover Pk/approximation algorithms/exact algorithms/parameter algorithms分类
信息技术与安全科学引用本文复制引用
王利民,华景煜..顶点Pk覆盖问题的研究综述[J].南京信息工程大学学报,2017,9(5):455-461,7.基金项目
国家自然科学基金(11471003,61425024) （11471003,61425024）
