跳到主要內容

臺灣博碩士論文加值系統

(44.221.66.130) 您好!臺灣時間:2024/06/20 23:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:蔡翔宇
研究生(外文):Shiang-Yu Tsai
論文名稱:分散式圖形同構演算法之設計與實驗分析
論文名稱(外文):A Distributed Graph Isomorphism Algorithm - Design and Experiment
指導教授:顏嗣鈞
指導教授(外文):Hsu-Chun Yen
學位類別:碩士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:中文
論文頁數:46
中文關鍵詞:分散式圖形同構演算法
外文關鍵詞:distributed algorithmisomorphism
相關次數:
  • 被引用被引用:0
  • 點閱點閱:336
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
科技的日新月異,不只為人類社會帶來變遷,連帶的在計算機科學中,也產生了了許多新的研究領域與問題。然而,許多新的研究問題看似與傳統無關,但其實是可以轉換為計算機領域中,研究已久的理論問題。
在計算機領域中,圖論(graph theory)是門重要的學問。幾乎各個計算機領域的主要問題,都可模塑到圖形的問題上,進而研究該問題的複雜度以及演算法。對於圖形(graph)的研究,已經有數百年的歷史;而近代的數學家及計算機科學家,則致力於探討圖形問題之複雜度,以及多項式時間演算法。
圖形理論中一個重要的問題,便是「圖形同構」(graph isomorphism)。本問題尚未找出多項式時間的演算法,也尚未被證明是否為NP-Complete之問題。然而,在工程應用上,許多重要的問題,可以簡化為圖形同構問題,也因此,許多經驗性的(heuristic)演算法被設計出來,以期在大部分普遍的情況下,能較有效率的解決圖形同構問題。
另外,隨著網路及運算的普及,分散式系統也漸漸的成為科學運算的重要途徑。藉由把一主要工作分成數個次要工作,交給每個運算節點(node),希望可以達到節省運算時間的目的。相關的論述及研究已有許多成果。
本文主要探討:在Brendan McKay提出的nauty演算法架構下,如何以分散式運算技術,改善其執行效率,並針對實驗結果,討論該演算法在分散式環境中之有利之處。
摘要 1
第1章 序論 2
1.1 研究動機 2
1.2 相關研究 4
1.3 論文貢獻 5
1.4 論文架構 6
第2章 基礎理論 7
2.1 問題定義 7
2.1.1 圖形(graph) 7
2.1.2 圖形同構問題(isomorphism) 7
2.2 基本定義 7
2.2.1 自同構序列 7
2.3 分割(PARTITION)與細緻化(REFINEMENT) 8
2.3.1 分割 8
2.3.2 分割細緻化(Refinement) 9
2.4 正規標籤(CANONICAL LABELS) 12
2.5 基本演算法 12
2.6 搜尋樹 12
2.7 圖形順序 18
2.8 利用自同構刪減狀態空間 18
第3章 分散式運算 23
3.1 MESSAGE PASSING INTERFACE 23
3.2 平行演算法 24
3.2.1 平行演算法之效率指標 24
3.3 平行回溯演算法(PARALLEL BACKTRACKING ALGORITHM) 25
3.3.1 平行式回溯演算法(Parallel Backtracking Algorithm) 27
第4章 分散式NAUTY演算法 30
4.1 主節點演算法 30
4.2 副節點演算法 34
第5章 實驗數據與分析 36
5.1 實驗環境 36
5.2 實驗數據與分析 36
5.2.1 Random General Graph 37
5.2.2 Regular 2D Mesh 39
5.2.3 Irregular 2D Mesh 41
5.3 綜合比較 43
第6章 結論 44
第7章 參考文獻 45
[1]J. R. Ullmann, “An algorithm for subgraph isomorphism”, Journal of the ACM, Volume 23, Issue 1, pp. 31-42, January 1976.
[2]D. C. Schmidt, L. E. Druffel, “A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices”, Journal of the ACM, Volume 23, Issue 3, pp. 433-445, July 1976.
[3]L.P. Cordella, P. Foggia, C. Sansone, M. Vento, “Evaluating performance of the VF graph matching algorithm”, Proc. of the 10th International Conference on Image Analysis and Processing, IEEE Computer Society Press, pp. 1172-1177, 1999.
[4]B. McKay, “Practical graph isomorphism”, Congr. Numer. 30, pp. 45-87, 1981.
[5]T. Miyazaki, “The complexity of Mckay''s canonical labeling algorithm”, In Groups and Computation II, pp. 239-256, 1995.
[6]P. Foggia, C. Sansone, M. Vento, “A performance comparison of five algorithms for graph isomorphism”, Proceedings of the 3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition, Italy, May 2001.
[7]C. Ebeling and O. Zajicek, “Validating VLSI Circuit Layout by Wirelist Comparison”, In Proceedings of the IEEE International Conference on Computer Aided Design (ICCAD-83) , pp. 172-173, September 1983.
[8]N. Giansiracusa, “Determining graph isomorphism via canonical labeling”
[9]S. G. Akl, “The design and analysis of parallel algorithms”, Prentice Hall, 1989.
[10]S. H. Roosta, “Parallel processing and parallel algorithms : theory and computation”, Springer, December 10, 1999.
[11]V. Kumar, A. Grama, A. Gupta, G. Karpis , “Introduction to parallel computing:design and analysis of parallel algorithms”, Benjamin-Cummings Pub Co, January 1994.
[12]P. Sanders, “Parallelizing NP-Complete Problems Using Tree Shaped Computations”, Journées de l''Informatique Messine (JIM). Metz, 1999.
[13]D. L. Kreher, “Combinatorial algorithms : generation, enumeration, and search”, CRC, December 18, 1998.
[14]R. Finkel, U. Manber, “DIB – A distributed implementation of backtracking”, ACM Transaction on Programming Languages and Systems, Vol. 9, No. 2, pp. 235-256, April 1987.
[15]M. Kouril, J. L. Paul, “A parallel backtracking framework (BkFr) for single and multiple clusters”, Proceedings of the 1st conference on computing frontiers, pp. 302-312, 2004.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top