請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43613
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 呂學一(Hsueh-I Lu) | |
dc.contributor.author | Ching-Chen Kuo | en |
dc.contributor.author | 郭慶徵 | zh_TW |
dc.date.accessioned | 2021-06-15T02:24:23Z | - |
dc.date.available | 2009-08-21 | |
dc.date.copyright | 2009-08-21 | |
dc.date.issued | 2009 | |
dc.date.submitted | 2009-08-18 | |
dc.identifier.citation | [1] R. Bubley and M. Dyer. Path coupling: a technique for proving rapid mixing in Markov chains. In Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, pages 223–231, 1997.
[2] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6(2):125–145, 2002. [3] M. Dyer, A. Flaxman, A. Frieze, and E. Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Structure and Algorithms, 29(4):450–465, 2006. [4] M. Dyer and A. Frieze. Randomly colouring graphs with lower bounds on girth and maximum degree. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 579–587, 2001. [5] M. Dyer, A. Frieze, T. P. Hayes, and E. Vigoda. Randomly coloring constant degree graphs. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pages 582–589, 2004. [6] M. Dyer, L. A. Goldberg, and M. Jerrum. Systematic scan for sampling colorings. Annals of Applied Probability, 16(1):185–230, 2006. [7] M. Dyer and C. Greenhill. On Markov chains for independent sets. Journal of Algorithms, 35(1):17–49, 2000. [8] M.Dyer, C. Greenhill, andM.Molloy. Very rapidmixing of the Glauber dynamics for proper colorings on bounded-degree graphs. Random Structure and Algorithms, 20(1):98–114,2002. [9] A. Frieze and J. Vera. On randomly colouring locally sparse graphs. Discrete Mathematics and Theoretical Computer Science, 8(1):121–128, 2006. [10] A. Frieze and E. Vigoda. A survey on the use ofMarkov chains to randomly sample colorings. In G. Grimmett and C.McDiarmid, editors, Combinatorics, Complexity, and Chance — A Tribute to Dominic Welsh, chapter 4. Oxford University Press,2007. [11] D. Galvin and P. Tetali. Slowmixing of Glauber dynamics for the hard-core model on regular bipartite graphs. Random Structure and Algorithms, 28(4):427–443, 2006. [12] T.Hayes and E.Vigoda. Anon-Markovian coupling for randomly sampling colorings. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. [13] T. P. Hayes. Local uniformity properties for Glauber dynamics on graph colorings.In submission. [14] T. P. Hayes. Randomly coloring graphs of girth at least five. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages 269–278, 2003. [15] T. P. Hayes and A. Sinclair. A general lower bound for mixing of single site dynamics on graphs. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 511–520, 2005. [16] T. P. Hayes, J. C. Vera, and E. Vigoda. Randomly coloring planar graphs with fewer colors than the maximum degree. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 450–458, 2007. [17] T. P. Hayes and E. Vigoda. Variable length path coupling. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 103–110, 2004. [18] T. P. Hayes and E. Vigoda. Coupling with stationary distribution and improved sampling for colorings and independent sets. In Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 971–979, 2005. [19] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963. [20] M. Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structure and Algorithms, 7(2):157–166, 1995. [21] M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration. In D. S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, pages 482–520. PWS Publishing Co., 1996. [22] M. Jerrum, L. Valiant, and V. Vazirani. Randomgeneration of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169–188,1986. [23] M. R. Jerrum. Counting, Sampling and Integrating: Algorithms and Complexity. Birkhauser Verlag, Basel, Switzerland, 2003. [24] C. Kenyon, E. Mossel, and Y. Peres. Glauber dynamics on trees and hyperbolic graphs. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001. [25] L. C. Lau and M. Molloy. Randomly colouring graphs with girth five and large maximumdegree. In Proceedings of the 7th Latin American Symposium on Theoretical Informatics, pages 665–676, 2006. [26] M. Luby and E. Vigoda. Fast convergence of the Glauber dynamics for sampling independent sets. Random Structure and Algorithms, 15(3-4):229–241, 1999. [27] D. Martin, G. L. Ann, G. Catherine, J. Mark, and M. Michael. An extension of path coupling and its application to the Glauber dynamics for graph colourings. In Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 616–624, 2000. [28] F.Martinelli and A. Sinclair. Mixing time for the solid-on-solid model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 571–580,2009. [29] F. Martinelli, A. Sinclair, and D. Weitz. Fast mixing for independent sets, colorings and other models on trees. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 456–465, 2004. [30] A. Sly. Reconstruction for the Potts model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 581–590, 2009. [31] E. Vigoda. Improved bounds for sampling colorings. Journal of Mathematical Physics, 41(3):1555–1569, 2000. [32] E. Vigoda. A note on the Glauber dynamics for sampling independent sets. Electronic Journal of Combinatorics, 8(1), 2001. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/43613 | - |
dc.description.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)。 | zh_TW |
dc.description.abstract | 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). | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T02:24:23Z (GMT). No. of bitstreams: 1 ntu-98-R96922074-1.pdf: 405710 bytes, checksum: c4ede601237743fba2397244541cc7c0 (MD5) Previous issue date: 2009 | en |
dc.description.tableofcontents | Acknowledgements ... i
Chinese Abstract ... ii English Abstract ... iii List of Tables ... vi 1 Introduction ... 1 1.1 Technical overview ... 3 1.2 Related work ... 4 2 Preliminaries ... 6 3 Rapid mixing on regular bipartite graphs... 9 3.1 Proof of Theorem 1.1(1) ... 25 4 Rapid mixing on graphs with bounded common neighbors... 28 4.1 Proof of Theorem 1.1(2) ... 31 Bibliography ...33 | |
dc.language.iso | en | |
dc.title | 正則雙分圖與有限共鄰圖上之隨機著色 | zh_TW |
dc.title | Randomly Coloring Regular Bipartite Graphs and Graphs with Bounded Common Neighbors | en |
dc.type | Thesis | |
dc.date.schoolyear | 97-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 何錦文,高明達 | |
dc.subject.keyword | 馬可夫鏈,隨機著色,圖,葛勞柏動態過程, | zh_TW |
dc.subject.keyword | Markov chai,random coloring,graph,Glauber dynamics, | en |
dc.relation.page | 37 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2009-08-18 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 396.2 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。