按:   检索词:   从
   最新录用    过刊检索
顶点Pk覆盖问题的研究综述
投稿时间:2017-07-04    点此下载全文
引用本文:王利民,华景煜.顶点Pk覆盖问题的研究综述[J].南京信息工程大学学报,2017,(5):455~461
摘要点击次数: 76
全文下载次数: 76
作者单位
王利民 南京大学 计算机科学与技术系, 南京, 210023 
华景煜 南京大学 计算机科学与技术系, 南京, 210023 
基金项目:国家自然科学基金(11471003,61425024)
中文摘要:顶点覆盖问题是经典的NP完全问题,在排序、计算机网络等现实生活中有许多的应用.近几年来,许多研究者开始探究它的推广形式——顶点Pk覆盖(VCPk)问题,即寻找一个顶点子集,从拓扑结构图中删除后使得剩下的顶点导出的子图不包含Pk路,其中Pk是指包含k个顶点的路.本文简单介绍了VCPk问题的应用背景,归纳了它在近似算法、精确算法、参数化算法3个方面的主要研究进展,并分析了一些主要的方法和技巧.在此基础上,对VCPk问题及其相关问题的研究前景进行了展望.
中文关键词:顶点Pk覆盖  近似算法  精确算法  参数化算法
 
A survey on vertex cover Pk problem
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阅读器

您是本站第 635016 位访问者
版权所有:南京信息工程大学期刊社《南京信息工程大学学报》编辑部     
地址:江苏南京,宁六路219号,南京信息工程大学