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

• 作者: 华景煜 王利民
• 来源期刊: 南京信息工程大学学报
• 学科: 工学
• 关键词: 顶点Pk覆盖 近似算法 精确算法 参数化算法
• 年，卷（期）: 2017,（5）
• 所属期刊栏目: 综述
• 页码范围: 455-461
• 页数: 7页
• 分类号: TP391.7
• 字数: 6525字
• 语种: 中文
• DOI: 10.13878/j.cnki.jnuist.2017.05.001

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王利民	南京大学计算机科学与技术系	3	15	1.0	3.0
2	华景煜	南京大学计算机科学与技术系	2	1	1.0	1.0