跳到主要內容

臺灣博碩士論文加值系統

(35.153.100.128) 您好!臺灣時間:2022/01/22 06:35
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:江耀軒
論文名稱:Cographs上的快速著色平行演算法
論文名稱(外文):A Fast Parallel Coloring Algorithm for Cographs
指導教授:謝孫源阮夙姿
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
論文頁數:46
中文關鍵詞:保距圖cographs著色問題著色數最小著色數-著色法
外文關鍵詞:distance-hereditary graphcographscoloring problemχ(G)-coloringχ(G)chromatic number
相關次數:
  • 被引用被引用:0
  • 點閱點閱:322
  • 評分評分:
  • 下載下載:53
  • 收藏至我的研究室書目清單書目收藏:0
cographs是一個不存在任何長度為3的生成路徑的圖。由於cographs屬於保距圖,所以具有保距圖的特性。若在一圖中取任意兩點u,v,在每個包含此兩點的連通生成子圖中,此兩點的距離保持不變。有這種特性的圖,稱為保距圖。著色法(coloring)是指一個無方向圖形G=(V, E)中的一個函數 c:V→N,使得邊集合E中的任意邊(u, v),都會滿足c(u)≠c(v)。此函數亦稱著色函數。若一著色法的著色函數為c:V→{1,..., k},其值域內最大整數值為k,則我們稱此著色法為k-著色法。最小著色數(chromatic number) 就是指滿足k-著色法的最小k值。對於圖形G的著色問題就是:找出最小著色數-著色法與最小著色數。本篇論文主要的目的為:對於任意的cograph,設計一個平行演算法以正確地找到一個最小著色數-著色法。而我們所設計出來的平行著色演算法,執行於處理器數量為 O(n/log n) 的EREW PRAM模式下,可以在時間複雜度O(log n)時間內做完。相較執行於CRCW PRAM模式下,G.S. Adhar提出的平行演算法 [14],我們的平行著色演算法:(1)減少了處理器的使用數量,從 O(n3) 減少為 O(log n) 。 (2)在比較沒有彈性的EREW PRAM模式下,所花費的時間複雜度為O(log n),少於G.S. Adhar在比較有彈性的CREW PRAM模式下的時間複雜度O(log2 n)。
目錄
中文摘要...................................ii
英文摘要(Abstract)........................iii
第一章 緒論
1.1 導論..................................1
1.2 研究成果..............................2
第二章 相關理論基礎........................3
第三章 平行著色演算法
3.1 平行著色演算法的主要概念.............11
3.2 相關理論與技術 ......................12
3.3 演算法分析 ..........................20
3.4 舉例與驗證 ..........................32
第四章 結論...............................41
參考文獻……………………………………………44
參考文獻
[1] J. Ja’ Ja’, An Introduction to Parallel Algorithm, Addison Wesley, 1992.
[2] P. L. Hammer and F. Maffray, Complete separable graphs, Discrete applied mathematics, 27(1):85-99, May 1990.
[3] D. G. Corneil, H. Lerchs, and L. S. Burlingham, Complement reducible graphs, Discrete Applied Mathematics, 3:163-174, 1981.
[4] L. Stewart, Cographs, A class of tree representable graphs, M. Sc. Thesis, TR 126/78, 1978.
[5] H. J. Bandelt and H. M. Mulder, Distance-hereditary graphs, Journal of Combinatorial Theory Series B,41(1):182-208, Augest 1989.
[6] S. -y. Hsieh, C.W. Ho, T. —s. Hsu, M. T. Ko, and G. H. Chen, Efficient parallel algorithms on distance-hereditary graphs, Parallel Processing Letters, 9(1):43-52, 1999.
[7] S. —y. Hsieh, C.W. Ho, T. —s. Hsu, M. T. Ko, and G. H. Chen, A fast implementation of a parallel tree contraction scheme and its application on distance-hereditary graphs, Journal of Algorithms, 35:50-81, 2000.
[8] S. —y. Hsieh, C.W. Ho, T. —s. Hsu, M. T. Ko, and G. H. Chen, Characterization of efficiently solvable problems on distance-hereditary graphs, Lecture Notes in Computer Science, vol. 1533:257-266, 1998.
[9] K. Abrahamson, N.dadoun, D. G. Kirpatick and T. Przytycka, A simple parallel tree contraction algorithm, Journal of Algorithms, 10:287-302, 1989.
[10] V. Chava’tal, Perfectly ordered Graphs, Annals of Discrete Mathematics, 21:63-65, 1984.
[11] Douglas B. West, Introduction to Graph Theory 2nd ed, Prentice-Hall Upper Saddle River, NJ07458.
[12] Xin He, Prallel algorithm for cogrpah recognition with applications, NSF grant CCR-9011214.
[13] Klaus Jansen, Complexity results for the optimum cost chromatic partition problem, Automata, Language and Programming, LNCS, 1256:727-737, 1997.
[14] G. S. Adhar, Parallel algorithms for cographs and parity graphs with applications, Journal of Algorithms, 11:252-284, 1990.
[15] A. Proskurowski, Recursive graphs, recursive labelings and shortest paths, SIAM J. Comput. 10, No. 9:391-397, 1981.
[16] M. S. Chang, S. Y. Hsieh, and G. H. Chen, Dynamic programming on distance-hereditary graphs, Proceedings of 7th International Symposium on Algorithms and Computation (ISAAC’97), LNCS 1350:344-353, 1997.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top