|
|||||
|
|
| 随机图点覆盖1度顶点核化算法分析 | |
| 引用本文： | 黄海滨,杨路明,陈建二,王建新,李绍华.随机图点覆盖1度顶点核化算法分析[J].小型微型计算机系统,2008,29(4):659-666. |
| 作者姓名： | 黄海滨 杨路明 陈建二 王建新 李绍华 |
| 作者单位： | 1. 中南大学,信息科学与工程学院,湖南,长沙,410083;玉林师范学院,数学与计算机科学系,广西,玉林,537000 2. 中南大学,信息科学与工程学院,湖南,长沙,410083 3. 中南大学,信息科学与工程学院,湖南,长沙,410083;德克萨斯A&M大学,计算机科学学院,美国,德克萨斯州,77843-3112 4. 中南大学,信息科学与工程学院,湖南,长沙,410083;广东商学院,计算机科学与技术系,广东,广州,510320 |
| 摘 要： | 将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力. |
| 关 键 词： | 参数计算 点覆盖 核化 随机图 生物计算 随机图 点覆盖 核化 算法分析 Graphs Random Vertex Cover 能力 度的把握 大小 随机度 意义 理论 方法 结果 实验 提取数据 BIND MIPS 重要推论 |
| 文章编号： | 1000-1220(2008)04-0659-08 |
| 修稿时间： | 2006年12月18 |
On Kernelization Algorithm of 1-Degree Vertex for Vertex Cover in Random Graphs |
|
| HUANG Hai-bin,YANG Lu-ming,CHEN Jian-er,WANG Jian-xin,LI Shao-hua.On Kernelization Algorithm of 1-Degree Vertex for Vertex Cover in Random Graphs[J].Mini-micro Systems,2008,29(4):659-666. | |
| Authors: | HUANG Hai-bin YANG Lu-ming CHEN Jian-er WANG Jian-xin LI Shao-hua |
| Affiliation: | HUANG Hai-bin1,2,YANG Lu-ming1,CHEN Jian-er1,3,WANG Jian-xin1,LI Shao-hua1,4 1(School of Information Science , Engineering,Central South University,Changsha 410083,China) 2(Department of Mathematics , Computer Science,Yulin Normal College,Yulin 537000,China) 3(Department of Computer Science,Texas A&M University,College Station,Texas 77843-3112,USA) 4(Department of Computer Science , Technology,Guangdong Commercial College,Guangzhuo 510320,China) |
| Abstract: | 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 an... |
| Keywords: | parameterized computation vertex cover kernelization random graphs biocomputing |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |