(44.192.112.123) 您好!臺灣時間:2021/03/07 16:47
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張堂峰
研究生(外文):TANG-FONG JHANG
論文名稱:簡單迴圈嵌入於超立方體
論文名稱(外文):Embedding of Simple Cycles in Hypercubes
指導教授:陳玉專
指導教授(外文):TANG-FONG JHANG
學位類別:碩士
校院名稱:明新科技大學
系所名稱:資訊管理研究所
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2011
畢業學年度:99
語文別:中文
論文頁數:35
中文關鍵詞:簡單迴圈簡單路徑嵌入迴圈超立方體
外文關鍵詞:simple cyclessimple pathscycle embeddinghypercube
相關次數:
  • 被引用被引用:0
  • 點閱點閱:86
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
一個連結網路(interconnection network)的基本拓樸(topology)通常用一個圖型(graph)G = (V, E)表示,其中V表示節點(vertex)集合,E表示邊(edge)集合。假設一個圖G能夠嵌入任意長度的k-迴圈(k-cycle)且迴圈長度範圍介於3 ≤ k ≤ |V(G)|我們稱此圖G為泛圈(pancyclic);假設一個圖G能夠嵌入任意偶數長度的k-迴圈且迴圈長度範圍介於4 ≤ k ≤ |V(G)|,我們稱此圖G為泛偶圈(bipancyclic)。
超立方體(hypercube)是一個廣受歡迎的網路,已經被廣泛地應用在平行系統上,並且有許多良好的網路拓樸性質,例如正則性(regularity)、小直徑(small diameter)、強度連通性(strong connectivity)、遞迴建構(recursive construction)、分割能力(partition ability)、相對低連結複雜度(relatively low link complexity)、簡易路由與廣播演算法(easy routing and broadcasting algorithms)等。
在連結網路中迴圈嵌入(cycle embedding)是很熱門的一個研究問題,因為它是一個重要測量工具,用來決定網路中的拓樸結構是否可嵌入各種不同長度的迴圈並加以應用。此外,在網路中嵌入不同長度的迴圈能夠有利於並行程序的執行效率,曾有許多文獻討論嵌入各種長度迴圈。在本研究中,我們在多維度的超立方體網路(n-dimensional hypercube network)Qn中,令邊e為 Qn 的任意一條邊,在本研究中我們討論在超立方體 Qn 上經過邊e的簡單k-迴圈數量,其k = 4、6、8。
The underlying topology of an interconnection network is usually modeled as a graph G = (V,E), in which V is the vertex set and E is the edge set. A graph G is pancyclic if any k-cycle can be embedded into it for 3 ≤ k ≤ |V(G)|; G is bipancyclic if any k-cycle of even length can be embedded into it for 4 ≤ k ≤ |V(G)|.
The hypercube is a popular network and it has been widely used in parallel systems. It also has many attractive properties, including regularity, symmetry, small diameter, strong connectivity, recursive construction, partition ability, relatively low link complexity, and easy routing and broadcasting algorithms.
The cycle embedding problem is one of the most popular research issues in interconnection networks, because it is an important measurement for determining whether the topology of a network is suitable for an application in which embedding rings of various lengths into the topology is required. Moreover, embedding cycles of different sizes into a network are benefit to execute parallel programs efficiently. There are many literatures which discussing cycle embedding of various lengths. Let edge e be any edge of the hypercube Qn . In this proposal, we discuss the number of simple k-cycles, which passing through the edge e for k = 4, 6, and 8 in the hypercube Qn .
摘要 ................................................... i
Abstract .............................................. ii
Contents .............................................. iii
List of Figures ....................................... iv
Chapter 1. Introduction ............................... 1
Chapter 2. Hypercubes ................................. 4
Chapter 3. Main Result ................................ 7
Chapter 4. Conclusions ................................ 25
References ............................................ 26
[1] J. A. Bondy and U. S. R. Murty, "Graph theory with applications", North Holland, New York, (1980).
[2] L. Bhuyan and D. P. Agrawal, "Generalized hypercube and hypercubes structures for a computer network," IEEE Transactions on Computers 33, pp. 323-333(1984)
[3] G. G. Cash, "The number of n-cycles in a graph," Applied Mathematics and Computation 184, pp. 1080-1083 (2007).
[4] Y. C. Chang and H. L. Fu, "The number of 6-cycles in a graph," Bulletin of the ICA 39, pp. 27-30 (2003).
[5] X. B. Chen, "Hamiltonian paths and cycles passing through a prescribed path in hypercubes," Information Processing Letters 110, pp. 77-82 (2009).
[6] H. Ding and Z. Huang, "Isomorphism identification of graphs: Especially for the graphs of kinematic chains," Mechanism and Machine Theory 44, pp. 122-139 (2009).
[7] Q. Dong and X. Yang, "Embedding a long faulty-free cycle in a crossed cube with more faulty vertices," Information Processing Letters 110, pp. 464-468 (2010).
[8] T. Dvorák, "Hamiltonian cycles with prescribed edges in hypercubes," SIAM Journal of Discrete Mathematics 19, pp. 135-144 (2005).
[9] J. Fan, X. Lin, Y. Pan and X. Jia, "Optimal fault-tolerant embedding of paths in twisted cubes," Journal of Parallel and Distributed Computing 67, pp. 205-214 (2007).
[10] J. Fan and Y. Xiao, "A method of counting the number of cycles in LDPC codes," International Conference of Signal Processing 3, pp. 2183-2186 (2006).
[11] F. F. Fang, "The bipancycle-connectivity of the hypercube," Information Sciences 178, pp. 4679-4687 (2008).
[12] J. F. Fang, "The bipancycle-connectivity of the hypercube, " Information Sciences 178, pp. 4679-4687 (2008).
[13] F. Harary and B. Manvel, "On the number of cycles in a graph," Mathematica Slovaca 21, pp. 55-63 (1971).
[14] L. Hongmei, "Cycles in enhanced hypercube networks," International Seminar on Future Information Technology and Management Engineering , pp. 560-563 (2008).
[15] S. Y. Hsieh, C. N. Kuo and H. H. Chou, "A further result on fault-free cycles in faulty folded hypercubes," Information Processing letters 110, pp. 41-43 (2009).
[16] S. Y. Hsieh, C. N. Kuo and H. L. Huang, "1-vertex-fault-tolerant cycles embedding on folded hypercubes," Discrete Applied Mathematics 157, pp. 3094-3098 (2009).
[17] S. Y. Hsieh and J. Y. Shiu, "Cycle embedding of augmented cubes," Applied Math- ematics and Computation 191, pp. 314-319 (2007).
[18] H. S. Hung, J. S. Fu and G. H. Chen, "Fault-free Hamiltonian cycles in crossed cubes with conditional link faults," Information Sciences 177, pp. 5664-5674 (2007)
[19] Y. R. Leu and S. Y. Kuo, "Distributed fault-tolerant ring embedding and reconguration in hypercubes," IEEE Transactions on Computers 48, pp. 81-88 (1999).
[20] T. K. Li, C. H. Tsai, Jimmy J. M. Tan, and L. H. Hsu, "Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes," Information Processing Letters 87, pp. 107-110 (2003).
[21] M. Ma and B. Liu, "Cycles embedding in exchanged hypercubes," Information Processing Letters 110, pp. 71-76 (2009).
[22] David F. Robinson, Dan Judd Philip K. Mckinley and Betty H. C. Cheng, "Efficient multicast in all-port wormhole-routed hypercubes," Journal of Parallel and Distributed Computing 31, pp. 126-140 (1995).
[23] Y. Saad and M. H. Schultz, "Topological properties of hypercubes," IEEE Transac-tions on Computers 37 (7), pp. 867-872 (1988).
[24] C. Troncoso, B. Gierlichs, B. Preneel, and I. Verbauwhede, "Perfect matching disclosure attacks," Privacy Enhancing Technologies–8th International Symposium, PETS 2008 5134, pp. 2-23 (2008).
[25] C. H. Tsai, "Fault-free cycles passing through prescribed paths in hypercubes with faulty edges," Applied Mathematics Letters 22, pp. 852-855 (2009).
[26] X. Wu, M. He, F. Wang, J. Yang, and S. Latify, "Distinct paths for the star graph," International Conference on Communications and Mobile Computing, pp. 322-326 (2009).
[27] P. J. Wan, "TWDM multichannel lightwave hypercube networks," Theoretical Computer Science 194, pp. 123-136 (1998).
[28] D. Xiang, "Unicast-based fault-tolerant multicasting in wormhole-routed hypercubes," Journal of Systems Architecture 54, pp. 1164-1178 (2008).
[29] J. M. Xu and M. Ma, "Cycles in folded hypercubes," Applied Mathematics Letters 19, pp. 140-145 (2006).
[30] M. Xu, X. D. Hu, and J. M. Xu, "Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes," Applied Mathematics and Computation 189, pp. 1393-1401 (2007).
[31] M. Xu and J. M. Xu, "Edge-pancyclicity of Möbius cubes," Information Processing Letters 96, pp. 136-140 (2005).
[32] M. C. Yang, "Edge-fault-tolerant node-pancyclicity of twisted cubes," Information Processing Letters 109, pp. 1206-1210 (2009).

連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔