跳到主要內容

臺灣博碩士論文加值系統

(44.192.22.242) 您好!臺灣時間:2021/08/03 19:31
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:凃昶任
研究生(外文):Chang-Jen Tu
論文名稱:局部雙扭超方體之邊互斥生成樹
論文名稱(外文):Edge-Disjoint Spanning Trees in Locally Twisted Cubes
指導教授:謝孫源
指導教授(外文):Sun-Yuan Hsieh
學位類別:碩士
校院名稱:國立成功大學
系所名稱:資訊工程學系碩博士班
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:英文
論文頁數:51
中文關鍵詞:平行演算法局部雙扭超方體互連網路漢彌路徑Latin square圖形理論邊互斥生成樹
外文關鍵詞:parallel algorithminterconnection networkslocally twisted cubesgraph-theoreticedge-disjoint spanning treeshamming distance Latin square
相關次數:
  • 被引用被引用:0
  • 點閱點閱:79
  • 評分評分:
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:0
在互連網路使用邊互斥生成樹對於資料擴散及傳播問題上提供了幾個優點,其中包含頻寬的增加及容錯增大等等。在這篇論文中,我們是第一個說明如何在局部雙扭超方體上去嵌入多顆邊互斥生成樹的相關問題,並且主要研究目標是使其能夠平行建構及數量為最多顆的生成樹。而主要的基本概念,是建構在所謂Latin square的觀念上,並且搭配我們發展出來有效率的平行演算法在局部雙扭超方體上建構邊互斥生成樹。
The use of edge-disjoint spanning trees for data broadcasting and scattering problem in networks provides a number of advantages, including the increase of bandwidth and fault-tolerance. In this thesis, we elucidate the problem of embedding multiple edge-disjoint spanning trees in locally twisted cubes with the objective of parallel and
maximum. Based on a simple concept called Latin square, we develop parallel algorithm to construct EDSTs in a locally twisted cubes efficiently.
Abstract(in Chinese) i
Abstract(in English) ii
Acknowledgement iii
Contents vii
List of Figures ix
List of Tables xi
1 Introduction 1
1.1 Motivation 4
1.2 Overview of the thesis 5
2 Preliminaries 7
2.1 Basic definition 8
2.2 Locally twisted cubes14
2.2.1 Basic definition 14
2.2.2 Extend property 18
2.3 Hamming distance 20
2.3.1 Basic definition 20
2.3.2 Special properties 20
2.3.3 History and applications 21
2.4 Latin square 21
2.4.1 Basic definition 21
2.4.2 Orthogonal array representation 22
2.4.3 Equivalence classes of Latin square 23
2.4.4 The number of Latin squares 23
2.4.5 Latin squares and error correcting codes 24
2.4.6 Latin squares and mathematical puzzles 25
2.4.7 HDLS 25
3 Constructing of Edge-Disjoint Spanning Trees on LTQn 27
4 Concluding Remarks 44
Bibliography 45
[1] S. B. Akers, D. Harel, and B. Krishnamurthy, "The Star Graph: An Attractive Alternative to the Hypercube," Proceedings of the International Conference on Parallel Processing, pp. 393--400, 1987.
[2] F. Bao, Y. Igarashi, and S. Ohring, "Reliable Broadcasting in Product Networks," Discrete Applied Mathematics, vol. 83, pp. 3--20, 1998.
[3] Q. Y. Chang, M. J. Ma, and J. M. Xu, "Fault-tolerant Pancyclicity of Locally Twisted Cubes," Journal of University of Science and Technology of China, vol. 36,
no. 6, pp. 607--610 and 673, 2006.
[4] Y. S. Chen, T. Y. Juang, and Y. Y. Shen, "Congestion-Free Embedding of 2(n-k) Spanning Trees in an Arrangement Graph," Journal of System Architecture,
vol. 47, pp. 73--86, 2001.
[5] J. Cheriyan and S. Maheshwari, "Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs," Journal of Algorithm, vol. 9,
pp. 507--537, 1988.
[6] S. A. Choudum and V. Sunitha, "Augmented Cubes," Networks, vol. 40, no. 2,pp. 71--84, 2002.
[7] I. Chung, "Application of the Special Latin Squares to the Parallel Routing Algorithm on Hypercube," Journal of Korean Information Science Society, vol. 19, no. 5, 1992.
[8] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, 2002.
[9] P. Cull and S. M. Larson, "The M�酣bius Cubes," IEEE Transactions on Computers, vol. 44, no. 5, pp. 647--659, 1995.
[10] S. Curran, O. Lee, and X. Yu, "Finding Four Independent Trees," SIAM Journal on Computing, vol. 35, pp. 1023--1058, 2006.
[11] K. Day and A. Tripathi, "Arrangement Graphs: A Class of Generalized Star Graphs," Information Processing Letters, vol. 42, no. 5, pp. 235--241, 1992.
[12] J. Denes and A. D. Keedwell, "Latin Squares and their Applications," Academic Press, 1974.
[13] E. Efe, "The Crossed Cube Architecture for Parallel Computation," IEEE Transactions on Parallel and Distributed Systems, vol. 3, no. 5, pp. 513--524, 1992.
[14] P. Fragopoulou, "Edge-Disjoint Spanning Trees on the Star Network with Applications to Fault Tolerance," IEEE Transactions on Computers, vol. 45, no. 2, pp. 174--185, 1996.
[15] P. Fragopoulou and S. G. Akl, "Optimal Communication Algorithms on Star Graphs Using Spanning Tree Constructions," Jounal of Parallel and Distributed
Computing, vol. 24, no. 1, pp. 55--71, 1995.
[16] P. Fraigniaud and C. T. Ho, "Arc-Disjoint Spanning Trees on the Cube-Connected-Cycles Network," Proceedings of the International Conference on Parallel Processing, vol. 1, pp. 225--229, 1991.
[17] J. S. Fu, "Fault-Tolerant Cycle Embedding in the Hypercube," Parallel Computing, vol. 29, no. 6, pp. 821--832, 2003.
[18] Z. Ge and S. L. Hakimi, "Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs," SIAM Journal on Computing, vol. 26, pp. 79--92, 1997.
[19] F. Harary, J. P. Hayes, and H. J. Wu, "A Survey of the Theory of Hypercube Graphs," Computational Mathematics and Applications, vol. 15, pp. 277--289, 1988.
[20] T. Hasunuma and H. Nagamochi, "Independent Spanning Trees with Small Depths in Iterated Line Digraphs," Discrete Aplied Mathematics, vol. 110, pp. 189--211, 2001.
[21] P. A. J. Hilbers, M. R. J. Koopman, and J. L. A. van de Snepscheut, "The Twisted Cube," Proceeding of the Conference on Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, pp. 152--159, 1987.
[22] D. W. Hillis, The Connection Machine. Camgridge: MIT Press, 1982.
[23] A. Huck, "Independent Trees in Planar Graphs," Graphs and Combinatorics, vol. 15, pp. 29--77, 1999.
[24] A. Itai and M. Rodeh, "The Multi-Tree Approach to Reliability in Distributed Networks," Information and Computation, vol. 79, pp. 43--59, 1988.
[25] Y. Iwasaki, Y. KAjiwara, K. Obokata, and Y. Igarashi, "Independent Spanning Trees of Chordal Rings," Information Processing Letters, vol. 69, pp. 155--160, 1999.
[26] S. L. Johnsson, "Communication E±cient Basic Linear Algebra Computations on Hypercube Architectures," Journal of Parallel and Distributed Computing, vol. 4, pp. 133--172, 1987.
[27] S. L. Johnsson and C. T. Ho, "Optimal Broadcasting and Personalized Communication in Hypercubes," IEEE Transactions on Computing, vol. 38, no. 9, pp. 1249--1268, 1989.
[28] A. Labourel, "Edge-Disjoint Spanning Trees in Triangulated Graphs on Surfaces and Application to Node Labeling," Preprint Submitted to Elsevier Science, 2006.
[29] S. Latifi, S. Zheng, and N. Bagherzadeh, "Optimal Ring Embedding in Hypercubes with Faulty Links," In Digest 22nd Symposium Fault-Tolerant Computing, pp. 178--184, 1992.
[30] C. T. Lin, "Embedding k(n-k) Edge-Disjoint Spanning Trees in Arrangement Graphs," Journal of Parallel and Distributed Computing, vol. 63, pp. 1277--1287, 2003.
[31] K. Miura, D. Takahashi, S. Nakano, and T. Nishizeki, "A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs," International Journal of Foundations of Computer Science, vol. 10, pp. 195--210, 1999.
[32] V. E. M. nad D. Sarkar, "Optimal Broadcasting on the Star Graph," IEEE Transactions Parallel and Distributed Systems, vol. 3, no. 4, pp. 389--396, 1992.
[33] S. Nagai and S. Nakano, "A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs," Proceedings of 26th Workshop on Graph-Theoretic Concepts in Computer Science, pp. 290--301, 2000.
[34] K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi, "Independent Spanning Trees of Product Graphs and their Construction," IEICE Transactions Fundamentals
of Electronics, Communications and Computer Sciences, vol. 79, pp. 1894--1903, 1996.
[35] B. Parhami, Introduction to Parallel Processing: Algorithms and Architectures. New Park: Plenum Press, 1999.
[36] M. O. Rabin, "Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance," Journal of the ACM, vol. 36, pp. 335--348, 1989.
[37] P. Ramanathan and K. G. Shin, "Reliable Broadcast in Hypercube Multicomputers," IEEE Transaction on Computing, vol. 37, no. 12, pp. 1654--1657, 1988.
[38] Y. Saad and M. H. Schultz, "Topological Properties of Hypercube," IEEE Transactions on Computers, vol. 37, pp. 867--872, 1988.
[39] J. P. Sheu, C. T. Wu, and T. S. Chen, "An Optimal Broadcasting Algorithm without Message Redundancy in Star Graphs," IEEE Transactions Parallel and Distributed Systems, vol. 6, no. 6, pp. 653--658, 1995.
[40] N. Singhvi and K. Ghose, "The Mcube: A Symmetrical Cube Based Network with Twisted Links," Proceeding of the 9th International Symposium of Parallel Processing, pp. 11--16, 1995.
[41] C. Stunkel, R. Sivaram, and D. Panda, "Implementing Multidestination Worms in Switch-Based Parallel Systems: Architectural Alternatives and their Impact," 24th ACM Annual International Symposium on Compter Architecture, 1997.
[42] T. Y. Sung, M. Y. Lin, and T. Y. Ho, "Multiple-Edge-Fault Tolerance with Respect to Hypercubes," IEEE Transactions on Parallel and Distributed Systems, vol. 8,
pp. 187--192, 1997.
[43] S. M. Tang, Y. L. Wang, and Y. H. Leu, "Optimal Independent Spanning Trees on Hypercubes," Journal of Information Science and Engineering, vol. 20, pp.
143--155, 2004.
[44] S. M. Tang, J. S. Yang, J. M. Chang, and Y. L. Wang, "Parallel Construction of Independent Spanning Trees on Multidimensional Tori," Proceeding of the 24th Workshop on Combinatorial Mathematics and Computation Theory, pp. 85--93, 2007.
[45] Y. C. Tseng, S. H. Chang, and J. P. Sheu, "Fault-Tolerant Ring Embedding in Star Graphs," IEEE Transactions Parallel and Distributed Systems, vol. 8, no. 12, pp. 1185--1195, 1997.
[46] Y. C. Tseng, T. Y. Juang, and C. J. Cnang, "Congestion-Free, Dilation-2 Embedding of Complete Binary Tree in Star Graphs," Networks, vol. 33, no. 3, pp.
221--231, 1999.
[47] Y. C. Tseng and J. P. Sheu, "Toward Optimal Broadcast in a Star Graph Using Multiple Spanning Trees," IEEE Transactions on Computers, vol. 46, no. 5, pp. 593--599, 1997.
[48] D. B. West, Introduction to Graph Theory, 2nd ed. Upper Saddle River, NJ: Prentice Hall, 2001.
[49] C. D. Wu, Optimal Fault-Tolerant Hamiltonicity of Star Graphs with Conditional Edge Faults. Taiwan: National Cheng Kung University, 2007.
[50] C. Y.Wu, Edge-Fault-Tolerant Hamiltonicity of Locally Twisted Cubes under Conditional Edge Faults. Taiwan: National Cheng Kung University, 2007.
[51] J. S. Yang, J. M. Chang, S. M. Tang, and Y. L. Wang, "Reducing the Height of Independent Spanning Trees in Chordal Rings," IEEE Transactions on Parallel and Distributed Systems, vol. 18, no. 5, 2007.
[52] J. S. Yang, J. M. Chang, Y. L. Wang, and S. M. Tang, "On the Independent Spanning Trees of Recursive Circulant Graphs G(cdm, d) with d >= 3," Proceeding of the 25th Workshop on Combinatorial Mathematics and Computation Theory, 2008.
[53] J. S. Yang, S. M. Tang, J. M. Chang, and Y. L. Wang, "Parallel Construction of Optimal Independent Spanning Trees on Hypercubes," Parallel Computing, vol. 33, pp. 73--79, 2007.
[54] X. Yang, D. Evans, and G. Megson, "The Locally Twisted Cubes," International Journal of Computer Mathematics, vol. 82, no. 4, pp. 401--413, 2005.
[55] P. Y. Yu, Node-Pancyclicity of Twisted Cubes. Taiwan: National Cheng Kung University, 2006.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top