Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43613
Title: | 正則雙分圖與有限共鄰圖上之隨機著色 Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors |
Authors: | Ching-Chen Kuo 郭慶徵 |
Advisor: | 呂學一(Hsueh-I Lu) |
Keyword: | 馬可夫鏈,隨機著色,圖,葛勞柏動態過程, Markov chai,random coloring,graph,Glauber dynamics, |
Publication Year : | 2009 |
Degree: | 碩士 |
Abstract: | 給定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 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-98-1.pdf Restricted Access | 396.2 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.