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

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

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题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.