顶点Pk覆盖问题的研究综述

来源：南京信息工程大学学报·自然科学版杂志2017年第5期北京时间：

作者：王利民

单位：王利民,南京大学 计算机科学与技术系, 南京, 210023,华景煜,南京大学 计算机科学与技术系, 南京, 210023

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

关键词：顶点Pk覆盖;近似算法;精确算法;参数化算法

基金资助：国家自然科学基金（11471003，61425024）