(3.236.228.250) 您好!臺灣時間:2021/04/17 13:16
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:呂昱翰
研究生(外文):Yu-Han Lyu
論文名稱:隨機產生k連通圖形
論文名稱(外文):Random Generating k-connected Graphs
指導教授:唐傳義
指導教授(外文):Chuan-Yi Tang
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2007
畢業學年度:95
語文別:英文
論文頁數:21
中文關鍵詞:蒙地卡羅馬可夫鍊隨機演算法
外文關鍵詞:Markov Chain Monte Carlo methodrandomized algorithmrapidly mixing
相關次數:
  • 被引用被引用:1
  • 點閱點閱:114
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
列舉組合物件在組合數學中一直都是重要的研究項目,而我們稱隨機產生組合物件的演算法為取樣。取樣在電腦科學中有很多的應用,像是程式正確性的測試等等,而且數學家也可以利用取樣的結果去驗證一些數學性質。
我們利用蒙地卡羅馬可夫鍊的方法設計出k 連通圖形的取樣方法,而我們可以證明出此方法可以近似均勻分布的產生k連通圖形,並且我們也證明了這演算法是快速收斂的。
Enumerating combinatorial objects is an important research topic in combinatorics. Algorithms for random generating combinatorial objects are called sampling. Sampling has many applications in computer science, for example program testing. Mathematicians
can use sampling to verify combinatorial property.
We developed a simple algorithm to sample k-connected graphs based on Markov Chain Monte Carlo method. This algorithm generates graphs at approximately uniform distribution, and we prove it is rapidly mixing
Abstract
Preface
Acknowledgements
Glossary of Notation
Table of Contents
1 Introduction 1
1.1 Combinatorial Generation
1.2 Markov Chain Monte Carlo Method
1.3 Previous Work
1.4 Contribution
1.5 Organization
2 Preliminaries
2.1 Graph Theory
2.2 Markov Chain
2.3 Markov Chain Monte Carlo Method
2.4 Mixing-time and Rapidly Mixing
2.5 Techniques for Analyzing Mixing-time
3 Algorithm
4 Mixing Time
5 Future Work
Epilogue
Appendix A Bibliography
[1] Be’la Bolloba’s. Random Graphs. Cambridge University Press, second edition, September 2001.
[2] R. Bubley and M. Dyer. Path coupling: A technique for proving rapid mixing in markov chains. In FOCS ’97: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97), page 223, Washington, DC, USA, 1997. IEEE Computer Society.
[3] M R Jerrum, L G Valiant, and V V Vazirani. Random generation of combinatorial structures from a uniform. Theoretical Computer Science, 43(2-3):169–188, 1986.
[4] Ravi Kannan, Prasad Tetali, and Santosh Vempala. Simple markov-chain algorithms for generating bipartite graphs and tournaments. In SODA ’97: Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, pages 193–200, Philadelphia, PA, USA, 1997. Society for Industrial and Applied Mathematics.
[5] J. H. Kim and V. H. Vu. Generating random regular graphs. Combinatorica, 26(6):683–708, 2006.
[6] Colin McDiarmid, Angelika Steger, and Dominic J. A. Welsh. Random planar graphs. Journal of Combinatorial Theory, Series B, 93(2):187–205, 2005.
[7] Guy Melancon and Fabrice Philippe. Generating connected acyclic digraphs uniformly at random. Information Processing Letters, 90(4):209–213, 2004.
[8] Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, January 2005.
[9] Dana Randall. Mixing. In FOCS ’03: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, page 4, Washington, DC, USA, 2003. IEEE Computer Society.
[10] Alistair Sinclair. Algorithms for random generation and counting: a Markov chain approach. Springer, February 1993.
[11] Alistair Sinclair and Mark Jerrum. Approximate counting, uniform generation and rapidly mixing markov chains. Information and Computation, 82(1):93–133, 1989.
[12] Richard P. Stanley. Enumerative Combinatorics, volume 1. Cambridge University Press, second edition, May 2000.
[13] Richard P. Stanley. Combinatorial generation. October 2003.
[14] Douglas B. West. Introduction to Graph Theory. Prentice Hall, second edition, Auguest 2000.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔