請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43613
標題: | 正則雙分圖與有限共鄰圖上之隨機著色 Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors |
作者: | Ching-Chen Kuo 郭慶徵 |
指導教授: | 呂學一(Hsueh-I Lu) |
關鍵字: | 馬可夫鏈,隨機著色,圖,葛勞柏動態過程, Markov chai,random coloring,graph,Glauber dynamics, |
出版年 : | 2009 |
學位: | 碩士 |
摘要: | 給定G是一個有n個點,最大度數為△的圖。葛勞柏動態過程是一個在G的所有著色上執行的馬可夫鏈。葛勞柏動態過程目前已被證明出在各種不同圖上可以達到快速趨近。近幾年來的研究焦點著重在△≧d log2 n,d是某些足夠大的常數。本篇論文結果如下:
1.給定α≒1.645為(1-e^{{-1}/x})^2+ 2xe^{-1/x}=2之根。若G為正則雙分圖,且k≥(α+ε) △,則葛勞柏動態過程的結合時間為O(nlog n)。 2. 給定β≒1.763為x=e^{1/x}之根。若G上任二相鄰點的共同鄰居個數至多為ε^{1.5}Delta/360e且k≥(1+ε)β△,則葛勞柏動態過程的結合時間為O(nlog n)。 Let G be an n-node graph with maximum degree △. The Glauber dynamics for G, defined by Jerrum, is a Markov chain over the k-colorings of G. Many classes of G on which the Glauber dynamics mixes rapidly have been identified. Recent research efforts focus on the important case that △≧d log_2 n holds for some sufficiently large constant d. We add the following new results along this direction, where ε can be any constant with 0 < ε < 1. 1. Let α≒1.645 be the root of (1-e^{{-1}/x})^2+ 2x e^{-1/x}=2. If G is regular and bipartite and k≥(α+ε) △, then the mixing time of the Glauber dynamics for G is O(nlog n). 2.Let β≒1.763 be the root of x=e^{1/x}. If the number of common neighbors for any two adjacent nodes of G is at most ε^{1.5}Delta/360e且k≥(1+ε)β△, then the mixing time of the Glauber dynamics is O(nlog n). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43613 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 396.2 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。