本文選題：隨機(jī)圖　切入點(diǎn)：植入團(tuán)　出處：《上海交通大學(xué)學(xué)報(bào)》2017年10期 　論文類(lèi)型：期刊論文

【摘要】：針對(duì)植入團(tuán)問(wèn)題是平均情況復(fù)雜性理論的一個(gè)中心問(wèn)題,將帶植入團(tuán)的隨機(jī)圖模型進(jìn)行推廣,提出小邊概率條件,使得邊概率可以隨著頂點(diǎn)數(shù)目的增大而變小.使用隨機(jī)算法分析中的概率工具,改進(jìn)文獻(xiàn)中算法的分析,證明在小邊概率條件下,存在以很大概率找到推廣模型中較小的植入團(tuán)的多項(xiàng)式時(shí)間隨機(jī)算法.
[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.
【作者單位】： 上海交通大學(xué)上海高校軟件理論研究中心;
【基金】：國(guó)家自然科學(xué)基金項(xiàng)目(61373029) 中德科學(xué)合作基金(GZ996)資助
【分類(lèi)號(hào)】：O157.5;TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 梅俊杰;劉蕻;許歡;王以松;;隨機(jī)圖的哈密爾頓回路實(shí)驗(yàn)研究[J];貴州大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年03期

2 林妤;許道云;;隨機(jī)圖G(2n,p)中k-匹配的相變性質(zhì)[J];貴州大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年01期

3 黃斌;吳春旺;鄭豐華;藺冰;;復(fù)雜網(wǎng)絡(luò)中隨機(jī)圖模型研究[J];計(jì)算機(jī)工程與科學(xué);2014年07期

4 王冰杰;;隨機(jī)圖在信息傳遞系統(tǒng)中的應(yīng)用[J];吉林師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2005年04期

5 譚利;侯振挺;;一類(lèi)無(wú)標(biāo)度隨機(jī)圖的度序列[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);2011年03期

6 王漢興;馬馳;;一類(lèi)隨機(jī)圖的演化(英文)[J];運(yùn)籌學(xué)學(xué)報(bào);2006年01期

7 陳志;范益政;杜文學(xué);;隨機(jī)圖的譜矩(英文)[J];應(yīng)用數(shù)學(xué);2011年04期

8 馬文麒,馬文麒,楊俊忠,胡崗;耦合映象格子凍結(jié)化隨機(jī)圖樣模式的動(dòng)力學(xué)特征(英文)[J];北京師范大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年01期

9 蔣輝;;頂點(diǎn)著色隨機(jī)圖邊數(shù)的中偏差[J];數(shù)學(xué)雜志;2008年01期

10 彭代淵;;隨機(jī)圖上的隨機(jī)游動(dòng)[J];西南交通大學(xué)學(xué)報(bào);1990年04期

相關(guān)博士學(xué)位論文 前4條

1 顏云志;有向無(wú)標(biāo)度圖與二項(xiàng)隨機(jī)圖圖因子[D];上海大學(xué);2007年

2 尚軼倫;隨機(jī)圖及對(duì)個(gè)體系統(tǒng)的一致性問(wèn)題[D];上海交通大學(xué);2010年

3 丁雪;隨機(jī)圖中若干矩陣的譜性質(zhì)[D];吉林大學(xué);2010年

4 于娜;獨(dú)立馬氏鏈邊隨機(jī)圖過(guò)程與隨機(jī)分枝樹(shù)研究[D];上海大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 劉亮;基于指數(shù)隨機(jī)圖的社會(huì)網(wǎng)絡(luò)構(gòu)建關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

2 李小慧;隨機(jī)圖的可約染色算法研究[D];蘭州交通大學(xué);2015年

3 尹波;隨機(jī)圖的色和可區(qū)別染色算法研究[D];蘭州交通大學(xué);2016年

4 胡騰云;隨機(jī)圖的D（β）染色算法研究[D];蘭州交通大學(xué);2016年

5 高雪嬌;3-參數(shù)指數(shù)隨機(jī)圖的生成與參數(shù)估計(jì)[D];吉林大學(xué);2017年

6 田甜;基于層次隨機(jī)圖模型的復(fù)雜腦網(wǎng)絡(luò)鏈路預(yù)測(cè)研究[D];太原理工大學(xué);2015年

7 賀國(guó)卿;隨機(jī)圖上頂點(diǎn)度數(shù)序列及樹(shù)分圖的分布[D];天津大學(xué);2010年

8 畢偉;具有隨機(jī)頂點(diǎn)權(quán)重的廣義隨機(jī)圖的極限定理[D];中國(guó)科學(xué)技術(shù)大學(xué);2014年

9 陳志;隨機(jī)圖的譜矩和Estrada指數(shù)[D];安徽大學(xué);2012年

10 劉紅;稀疏隨機(jī)圖中孤立點(diǎn)的個(gè)數(shù)的偏差不等式與中偏差[D];武漢大學(xué);2005年

，

本文編號(hào)：1636234