顶点覆盖k-路问题

项目名称： 顶点覆盖k-路问题

项目编号： No.11201021

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 涂建华

作者单位： 北京化工大学

项目金额： 22万元

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

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

英文摘要： The vertex cover problem is one of the most classical NP-hard problems in combinatorial optimization and computer science. Erd?s (International Mathematician, Wolf Prize winner) and other scientists generalized it into the vertex cover certain types of subgraph problems. The generalized problems, closely correlating with approximation algorithm theory and computational complexity theory, are the hot research topics in graph theory in recent two decades. The vertex cover k-path problem is one of the generalized problems. And, the study on the vertex cover k-path problem also has important links with other topics of graph theory. Meanwhile, the vertex cover k-path problem can be applied on two important real cases. This project will study the vertex cover k-path problem from two aspects. First, from the algorithmic perspective, we will determine the algorithmic complexity of some problems and give approximation algorithms or polynomial time exact algorithms. In general cases, we will design some approximation algorithms for the vertex cover k-path problem which work for any integer k. On the other hand, we want to get some results on the vertex cover k-path number. We plan to combine the classical method in graph theory and the probabilistic method to find the relationships between the vertex cover k-pat

英文关键词： The vertex cover k-path problem；Graph algorithm；Computational complexity；Approximation algorithm；Vertex cover k-path number