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