| 顶点Pk覆盖问题的研究综述 |
| |
| 引用本文： | 王利民,华景煜.顶点Pk覆盖问题的研究综述[J].南京气象学院学报,2017,9(5):455-461. |
| |
| 作者姓名： | 王利民 华景煜 |
| |
| 作者单位： | 南京大学 计算机科学与技术系, 南京, 210023,南京大学 计算机科学与技术系, 南京, 210023 |
| |
| 基金项目： | 国家自然科学基金（11471003，61425024） |
| |
| 摘 要： | 顶点覆盖问题是经典的NP完全问题，在排序、计算机网络等现实生活中有许多的应用.近几年来，许多研究者开始探究它的推广形式——顶点Pk覆盖（VCPk）问题，即寻找一个顶点子集，从拓扑结构图中删除后使得剩下的顶点导出的子图不包含Pk路，其中Pk是指包含k个顶点的路.本文简单介绍了VCPk问题的应用背景，归纳了它在近似算法、精确算法、参数化算法3个方面的主要研究进展，并分析了一些主要的方法和技巧.在此基础上，对VCPk问题及其相关问题的研究前景进行了展望.
|
| 关 键 词： | 顶点Pk覆盖 近似算法 精确算法 参数化算法 |
| 收稿时间： | 2017/7/4 0:00:00 |
A survey on vertex cover Pk problem |
| |
| WANG Limin and HUA Jingyu.A survey on vertex cover Pk problem[J].Journal of Nanjing Institute of Meteorology,2017,9(5):455-461. |
| |
| Authors: | WANG Limin and HUA Jingyu |
| |
| Institution: | Department of Computer Science and Technology, Nanjing University, Nanjing 210023 and Department of Computer Science and Technology, Nanjing University, Nanjing 210023 |
| |
| 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. |
| |
| Keywords: | vertex cover Pk approximation algorithms exact algorithms parameter algorithms |
|
| 点击此处可从《南京气象学院学报》浏览原始摘要信息 |
| 点击此处可从《南京气象学院学报》下载免费的PDF全文 |
|
