东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

基于子图的随机图点覆盖2度点核化研究

ISSN号：1000-1239
期刊名称：《计算机研究与发展》
时间：0
分类：O153.1[理学—数学;理学—基础数学] O157.5[理学—数学;理学—基础数学]
作者机构：[1]中南大学信息科学与工程学院,长沙410083, [2]玉林师范学院数学与计算机科学系,广西玉林537000, [3]德克萨斯A＆M大学计算机科学系,美国德克萨斯大学城77843—3112, [4]广东商学院计算机科学与技术系,广州510320
相关基金：国家自然科学基金重点项目（60433020）

作者：黄海滨[1,2], 杨路明[1], 王建新[1], 陈建二[1,3], 李绍华[1,4]

关键词：子图计数, 核化, 点覆盖, 参数计算, 随机图, subgraph count kernelization, vertex cover, parameterized computation, random graph

中文摘要：

点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形子图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论：2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ（x）的随机图的参数化点覆盖问题（G,k）,当k小于某一与φ（x）有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.

英文摘要：

While the exact solution to vertex cover problem can be found within the frame of parameterized computation, there are some limits in the theory and practice, due to the lacking both in the analysis of algorithms mechanism and process and in the grasp of problems macroscopical and dynamic properties. On the basis of fixed-parameter tractability, the d-decision makable by way of kernelization （d-DMK） of the parameterized vertex cover problem of random graph is put forward and the counting method for triangle subgraphs with 2-degree vertex is also presented. According to the studies of the sharing relationship of the vertex between the subgraphs, the dynamic and evolvement mechanism of the kernel and the degree distribution in the process of 2-degree vertex kernelization are described, from which two deductions are drawn： the first states that the strength of the kernelization algorithm based on 2-degree gets its maximum in a random graph when the probability of its 2-degree vertex is about 0.75; the second states that the parameterized vertex cover problem （G, k） of random graph given by φ（x） is 2-DMK when k smaller than a given value relation to φ（x）. The results of the emulation show that the theory can not only deal with the mechanism of the kernelization, but also offer an effective way to analyze such an NP-completeness problem in random graph and a new method to solve a class of uncertain problems with known degree distrib utions.

同期刊论文项目