-
题名基于子图的随机图点覆盖2度点核化研究
- 1
-
-
作者
黄海滨
杨路明
王建新
陈建二
李绍华
-
机构
中南大学信息科学与工程学院
玉林师范学院数学与计算机科学系
德克萨斯A&M大学计算机科学系
广东商学院计算机科学与技术系
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2009年第1期31-40,共10页
-
基金
国家自然科学基金重点项目(60433020)~~
-
文摘
点覆盖问题虽然可以在参数计算理论的架构内求精确解,但是目前在理论及应用上有一定的局限性.根据不同度的顶点之间及顶点与边的关系,提出随机图参数化点覆盖问题的d-核化可决策性及2度点三角形子图的计数方法;通过研究子图对顶点的共享关系,分析2度顶点核化过程中核及度分布演变的动态过程,得出随机图2度点核化强度与2度点概率关系及2度点核化可决策性的两个推论:2度点核化算法对2度点分布概率约为0.75的随机图的核化强度最高;对顶点度概率分布为φ(x)的随机图的参数化点覆盖问题(G,k),当k小于某一与φ(x)有关的值时,它是2-核化可决策的.仿真结果证实,该理论能够把握2度点核化的内在机制,提供随机图上这一NP完全问题的求解方法,也为参数计算在已知度分布的一类不确定问题中的应用提供了可能.
-
关键词
子图计数
核化
点覆盖
参数计算
随机图
-
Keywords
subgraph count kernelization
vertex cover
parameterized computation
random graph
-
分类号
O153.1
[理学—数学]
O157.5
[理学—基础数学]
-
