小边概率条件下较小植入团的算法

发布时间：2018-03-19 22:22

  本文选题：随机图　切入点：植入团　出处：《上海交通大学学报》2017年10期 　论文类型：期刊论文

【摘要】：针对植入团问题是平均情况复杂性理论的一个中心问题,将带植入团的随机图模型进行推广,提出小边概率条件,使得边概率可以随着顶点数目的增大而变小.使用随机算法分析中的概率工具,改进文献中算法的分析,证明在小边概率条件下,存在以很大概率找到推广模型中较小的植入团的多项式时间随机算法.
[Abstract]:In view of the fact that the implant problem is a central problem in the theory of average case complexity, the random graph model with implants is generalized, and the small edge probability condition is proposed. The edge probability can be reduced with the increase of the number of vertices. Using the probabilistic tool in random algorithm analysis, we improve the analysis of the algorithm in the literature, and prove that under the condition of small edge probability, There is a polynomial time random algorithm with high probability to find smaller implants in the extended model.
【作者单位】： 上海交通大学上海高校软件理论研究中心;
【基金】：国家自然科学基金项目(61373029) 中德科学合作基金(GZ996)资助
【分类号】：O157.5;TP301.6

【相似文献】

相关期刊论文 前10条

1 梅俊杰;刘蕻;许欢;王以松;;随机图的哈密尔顿回路实验研究[J];贵州大学学报(自然科学版);2013年03期

2 林妤;许道云;;随机图G(2n,p)中k-匹配的相变性质[J];贵州大学学报(自然科学版);2014年01期

3 黄斌;吴春旺;郑丰华;蔺冰;;复杂网络中随机图模型研究[J];计算机工程与科学;2014年07期

4 王冰杰;;随机图在信息传递系统中的应用[J];吉林师范大学学报(自然科学版);2005年04期

5 谭利;侯振挺;;一类无标度随机图的度序列[J];应用数学学报;2011年03期

6 王汉兴;马驰;;一类随机图的演化(英文)[J];运筹学学报;2006年01期

7 陈志;范益政;杜文学;;随机图的谱矩(英文)[J];应用数学;2011年04期

8 马文麒,马文麒,杨俊忠,胡岗;耦合映象格子冻结化随机图样模式的动力学特征(英文)[J];北京师范大学学报(自然科学版);1999年01期

9 蒋辉;;顶点着色随机图边数的中偏差[J];数学杂志;2008年01期

10 彭代渊;;随机图上的随机游动[J];西南交通大学学报;1990年04期

相关博士学位论文 前4条

1 颜云志;有向无标度图与二项随机图图因子[D];上海大学;2007年

2 尚轶伦;随机图及对个体系统的一致性问题[D];上海交通大学;2010年

3 丁雪;随机图中若干矩阵的谱性质[D];吉林大学;2010年

4 于娜;独立马氏链边随机图过程与随机分枝树研究[D];上海大学;2012年

相关硕士学位论文 前10条

1 刘亮;基于指数随机图的社会网络构建关键技术研究[D];国防科学技术大学;2013年

2 李小慧;随机图的可约染色算法研究[D];兰州交通大学;2015年

3 尹波;随机图的色和可区别染色算法研究[D];兰州交通大学;2016年

4 胡腾云;随机图的D（β）染色算法研究[D];兰州交通大学;2016年

5 高雪娇;3-参数指数随机图的生成与参数估计[D];吉林大学;2017年

6 田甜;基于层次随机图模型的复杂脑网络链路预测研究[D];太原理工大学;2015年

7 贺国卿;随机图上顶点度数序列及树分图的分布[D];天津大学;2010年

8 毕伟;具有随机顶点权重的广义随机图的极限定理[D];中国科学技术大学;2014年

9 陈志;随机图的谱矩和Estrada指数[D];安徽大学;2012年

10 刘红;稀疏随机图中孤立点的个数的偏差不等式与中偏差[D];武汉大学;2005年

，

本文编号：1636234