随机图点覆盖1度顶点核化算法分析  

On Kernelization Algorithm of 1-Degree Vertex for Vertex Cover in Random Graphs

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

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083 [2]玉林师范学院数学与计算机科学系,广西玉林537000 [3]德克萨斯A&M大学计算机科学学院,美国德克萨斯州77843-3112 [4]广东商学院计算机科学与技术系,广东广州510320

出　　处：《小型微型计算机系统》2008年第4期659-666,共8页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(60433020)资助

摘　　要：将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.Introducing random graphs into the realm of parameterized computation, this paper investigates the inherence and evolvement laws of the kernel and the degree distribution in the process of 1-degree vertex kernelization from their statistic properties and probability methods, and gets two deductions; one is about the relationship between the strength of 1-degree vertex kernelization and average degree, the other is about the relationship between the decision-making of the vertex cover problem of random graphs and degree distribution. The results of 1-degree vertex kernelization experiments and analysis of the data from MIPS and BIND show at last, that the methods put forward here are not only meaningful in theory but also able to hold a practical problem to a certain extent according to its randomization degree.

关 键 词：参数计算 点覆盖 核化 随机图 生物计算 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]