欢迎访问发表云网!为您提供杂志订阅、期刊投稿咨询服务!

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

王利民; 华景煜 南京大学计算机科学与技术系; 南京210023
顶点pk覆盖   近似算法   精确算法   参数化算法  

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

简介:《南京信息工程大学学报·自然科学版》(CN:32-1801/N)是一本有较高学术价值的大型双月刊,自创刊以来,选题新奇而不失报道广度,服务大众而不失理论高度。颇受业界和广大读者的关注和好评。

注:因版权方要求,不能公开全文,如需全文,请咨询杂志社

关注 19人评论|0人关注
服务与支持