顶点覆盖k-路问题-东篱科研大数据发现系统（DRDS）

位置：立项数据库 > 立项详情页

顶点覆盖k-路问题

项目名称：顶点覆盖k-路问题
项目类别：青年科学基金项目
批准号：11201021
申请代码：A011602
项目来源：国家自然科学基金
研究期限：2013-01-01-2015-12-31

项目负责人：涂建华
依托单位：北京化工大学
批准年度：2012

中文摘要：

顶点覆盖问题是组合优化和计算机科学领域最经典NP难问题之一，Erd?s(国际数学大师，Wolf 奖得主)等人把它推广成了顶点覆盖某类子图问题。这类推广问题，与近似算法理论和计算复杂性理论有着紧密联系，是近二十年来图论研究的热点问题。顶点覆盖k-路问题也属于这类推广的问题。同时，顶点覆盖k-路问题的研究，与图论的其他课题也有着重要联系，且在两类实际问题中有着重要应用。本项目将从两个方面来研究顶点覆盖k-路问题。首先，我们从算法的角度研究顶点覆盖k-路问题，确定某些问题的算法复杂性，给出这些问题的近似算法或多项式时间的精确算法。设计k为一般情况下的顶点覆盖k-路问题的近似算法。另一方面，我们研究顶点覆盖k-路数。将经典图论中的方法与概率方法相结合，来研究图的顶点覆盖k-路数与图的若干其他不变量（最大度、直径、半径、围长等）的关系，给出图的顶点覆盖k-路数的上下界，或者精确值。

中文主题词：顶点覆盖k-路问题；图论算法；算法复杂性；近似算法；顶点覆盖k-路数

结论摘要：

英文主题词The vertex cover k-path problem；Graph algorithm；Computational complexity；Approximation algorithm；Vertex cover k-path number

成果综合统计