(3.215.180.226) 您好!臺灣時間:2021/03/06 13:38
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:楊廷鈞
研究生(外文):Ting-Jyun Yang
論文名稱:在扭曲立方體的連結網路上以簡單的平行方法建構獨立擴展樹
論文名稱(外文):A Simple Parallel Algorithm for Constructing Independent Spanning Trees on Twisted Cubes
指導教授:陳恩航陳恩航引用關係
指導教授(外文):An-Hang Chen
學位類別:碩士
校院名稱:國立臺北商業技術學院
系所名稱:資訊與決策科學研究所
學門:電算機學門
學類:電算機應用學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:39
中文關鍵詞:立方體獨立擴展樹連結網路扭曲立方體平行演算法
外文關鍵詞:HypercubeIndependent spanning treesInterconnection networksTwisted cubesParallel algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:47
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
在1989年時, Zehavi 和 Itai [ Three tree-paths, J. Graph Theory, (1989) ] 提出了以下的猜測:在一個 k 連通度的圖 G 中一定會有 k 棵以任意點為根的獨 立擴展樹。一個 n 維度的扭轉立方體記為 TQn,扭轉立方體是超立方體的變 形。2010年時, Yang [ Constructing edge-disjoint spanning trees in twisted cubes Inform. Sci., (2010) ] 提出可在奇數維度扭轉立方體建構邊互斥擴展樹的演算法。 同時,Yang 發現其中一半的樹是獨立擴展樹。在這之後 Wang 等人 [ Independent spanning trees on twisted cubes, J. Parallel Distrib. Comput., (2012) ] 證明在 TQn 上以任意點為根來建立獨立擴展樹的演算法,時間複雜度為 O(N log N ),N = 2^n 為 TQn 中所有點的數量。然而,這種演算法以遞迴方式執行,很難被平行化。在 本文中,我們提出了一個非遞迴且完全平行的演算法,在 TQn 建構一個任意節點為根的獨立擴展樹,同時使用 N 個處理器,時間複雜度為 O(logN)。特別值得一提是建構擴展樹的規則很容易並且獨立性的證明是比過去 Yang [ Constructing edge-disjoint spanning trees in twisted cubes Inform. Sci., (2010) ] 更簡單。
In 1989, Zehavi and Itai [ Three tree-paths, J. Graph Theory, (1989) ] proposed the following conjecture: a k-connected graph G must possess k independent span- ning trees (ISTs for short) with an arbitrary node as the root. An n-dimensional twisted cube, denoted by TQn, is a variation of hypercubes with connectivity n to achieving some improvements of structure properties. 2010, Yang [ Constructing edge-disjoint spanning trees in twisted cubes Inform. Sci., (2010) ] proposed an al- gorithm for constructing n edge-disjoint spanning trees in TQn for any odd integer n ≧ 3. Moreover, he showed that half of them are ISTs. At a later stage, Wang et al. [ Independent spanning trees on twisted cubes, J. Parallel Distrib. Comput., (2012) ] confirm the ISTs conjecture by providing an O(N log N ) algorithm to construct n ISTs rooted at an arbitrary node on TQn, where N = 2^n is the number of nodes in TQn. However, this algorithm is executed in a recursive fashion and thus are hard to be parallelized. In this thesis, we present a non-recursive and fully parallelized approach to construct n ISTs rooted at an arbitrary node of TQn in O(logN) time with N processors. In particular, the constructed rule of spanning trees is simple and the proof of independency is easier than ever before.
書名頁 ........................................ I
論文口試委員審定書................................ II
摘要 ........................................ III
Abstract ........................................ IV
誌謝 ........................................ VI
Contents........................................ VIII
List of Tables........................................ X
List of Figures........................................ XI
1 Introduction................................. 1
1.1 Background ................................ 1
1.2 Motivation and Intentions ........................ 4
1.3 Outline of the Thesis........................... 5
2 InterconnectionNetworks ........................ 6
2.1 Hypercubes ................................ 8
2.2 TwistedCubes .............................. 9
3 RelatedWorks ............................... 14
4 Independent Spanning Trees on Twisted Cubes . . . . . . . . . . 16
4.1 Constructing ISTs on Twisted Cubes in Parallel . . . . . . . . . . . 16
4.2 Correctness ................................ 30
5 Conclusion and remarks ......................... 34
Bibliography ........................................ 35
[1] S. Abraham and K. Padmanabhan, The twisted cube topology for multiproces- sors: a study in network asymmetry, J. Parallel Distrib. Comput., 13 (1991) 104–110.
[2] F. Bao, Y. Funyu, Y. Hamada and Y. Igarashi, Reliable broadcasting and secure distributing in channel networks, in: Proc. of 3rd International Symposium on Parallel Architectures, Algorithms and Networks, ISPAN’97, Taipei, December 1997, 472–478.
[3] ] C.-P. Chang, J.-N. Wang, L.-H. Hsu, Topological properties of twisted cubes, Inform. Sci., 113 (1999) 147–167.
[4] X.-B. Chen, Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs, Inform. Process. Lett., 111 (2011) 235– 238.
[5] B. Cheng, J. Fan, X. Jia, and J. Jia, Parallel construction of independent spanning trees and an application in diagnosis on Möbius cubes, J. Supercomput., 65 (2013) 1279–1301.
[6] B. Cheng, J. Fan, X. Jia, and J. Wang, Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes, J. Parallel Distrib. Comput., 73 (2013) 641–652.
[7] B. Cheng, J. Fan, X. Jia, and S. Zhang, Independent spanning trees in crossed cubes, Inform. Sci., 233 (2013) 276–289.
[8] B. Cheng, J. Fan, X. Jia, S. Zhang, and B. Chen, Constructive algorithm of independent spanning trees on M ̈obius cubes, Comput. J., 56 (2013) 1347–1362.
[9] J. Cheriyan and S.N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms, 9 (1988) 507–537.
[10] P. Cull and S.M. Larson, The Mo ̈bius cubes, IEEE Trans. Comput., 44 (1995) 647–659.
[11] S. Curran, O. Lee and X. Yu, Finding four independent trees, SIAM Journal on Computing, 35 (2006) 1023–1058.
[12] J. Fan, X. Jia, X. Lin, Optimal embeddings of paths with various lengths in twisted cubes, IEEE Trans. Parallel Distrib. Syst., 18 (2007) 511–521.
[13] J. Fan, X. Jia, X. Lin, Embedding of cycles in twisted cubes with edge-pancyclic, Algorithmica, 51(2008) 264–282.
[14] J. Fan, X. Lin, Y. Pan, X. Jia, Optimal fault-tolerant embedding of paths in twisted cubes, IEEE Trans. Parallel Distrib. Syst., 67 (2007) 205–214.
[15] J.-S. Fu, Fault-free Hamiltonian cycles in twisted cubes with conditional link faults, Theoret. Comput. Sci., 407 (2008) 318–329.
[16] P.A.J. Hilbers, M.R.J. Koopman, J.L.A. van de Snepscheut, The twisted cube, in: PARLE: Parallel Architectures and Languages Europe, Vol. 1: Parallel Architectures, Lecture Notes in Computer Science, Vol. 258, 1987, pp. 152-159
[17] W.-T. Huang, J.-M. Tan, C.-N. Hung, L.-H. Hsu, Fault-tolerant Hamiltonicity of twisted cubes, J. Parallel Distrib. Comput., 62 (2002) 591–604.
[18] A. Huck, Independent trees in graphs, Graphs Combin., 10 (1994) 29–45.
[19] A. Huck, Independent trees in planar graphs, Graphs Combin., 15 (1999) 29–77.
[20] A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Inform. Comput., 79 (1988) 43–59.
[21] Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, Independent spanning trees of chordal rings, Inform. Process. Lett., 69 (1999) 155–160.
[22] J.-S. Kim, H.-O. Lee, E. Cheng, and L. Lipt ́ak, Optimal independent spanning trees on odd graphs, J. Supercomputing, 56 (2011) 212–225.
[23] J.-S. Kim, H.-O. Lee, E. Cheng, and L. Lipta ́k, Independent spanning trees on even networks, Inform. Sci., 181 (2011) 2892–2905.
[24] P.D. Kulasinghe and S. Bettayeb, Multiply-twisted hypercube with 5 or more dimensions is not node transitive, Inform. Process. Lett., 53 (1995) 33–36.
[25] C.-J. Lai, C.-H. Tsai, Embedding a family of meshes into twisted cubes, Inform.Process. Lett., 108 (2008) 326–330.
[26] P.-L. Lai, C.-H. Tsai, Embedding of tori and grids into twisted cubes, Theoret. Comput. Sci., 411 (2010) 3763–3773.
[27] Y-J. Liu, J.K. Lan, W.Y. Chou, and C. Chen, Constructing independent spanning trees for locally twisted cubes, Theoret. Comput. Sci., 412 (2011) 2237–2252.
[28] K. Miura, S. Nakano, T. Nishizeki, and D. Takahashi, A linear-time algorithm to find four independent spanning trees in four connected planar graphs, Internat. J. Found. Comput. Sci., 10 (1999) 195–210.
[29] S. Nagai and S. Nakano, A linear-time algorithm to find independent spanning trees in maximal planar graphs, IEICE Trans. Fund. Electron. Comm. Comput. Sci., E84-A (2001) 1102–1109.
[30] K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi, Independent spanning trees of product graphs and their construction, IEICE Trans. Fund. Electron. Comm. Comput. Sci., E79-A (1996) 1894–1903.
[31] T.M. Pinkston and J. Duato, Interconnection Networks, Retrieved from Massachusetts Institute of Technology, Institute for Learning Technologies Web site: http://web.mit.edu/6.173/www/currentsemester/readings/R07- interconnection-networks-hennessy-patterson.pdf
[32] A.A. Rescigno, node-disjoint spanning trees of the star network with applica- tions to fault-tolerance and security, Inform. Sci., 137 (2001) 259–276.
[33] Y. Saad and M.H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput., 37 (1988) 867–872.
[34] S.-M. Tang, Y.-L. Wang, and Y.-H. Leu, Optimal independent spanning trees on hypercubes, J. Inform. Sci. Eng., 20 (2004) 143–155.
[35] S.-M. Tang, J.-S. Yang, Y.-L. Wang, and J.-M. Chang, Independent spanning trees on multidimensional torus networks, IEEE Trans. Comput., 59 (2010) 93–102.
[36] Y. Wang, J. Fan, G. Zhou, and X. Jia, Independent spanning trees on twisted cubes, J. Parallel Distrib. Comput., 72 (2012) 58–69.
[37] Y. Wang, J. Fan, X. Jia, and H. Huang, An algorithm to construct independent spanning trees on parity cubes, Theoret. Comput. Sci., 465 (2012) 61–72.
[38] J. Werapun, S. Intakosum, and V. Boonjing, An efficient parallel construction of optimal independent spanning trees on hypercubes, J. Parallel Distrib. Comput., 72 (2012) 1713–1724.
[39] J.-S. Yang, H.-C. Chan, and J.-M. Chang, Broadcasting secure messages via optimal independent spanning trees in folded hypercubes, Discrete Appl. Math., 159 (2011) 1254–1263.
[40] J.-S. Yang and J.-M. Chang, Independent spanning trees on folded hyper-stars, Networks, 56 (2010) 272–281.
[41] J.-S. Yang and J.-M. Chang, Optimal independent spanning trees on Cartesian product of hybrid graphs, Comput. J., 57 (2014) 93–99.
[42] J.-S. Yang, J.-M. Chang, S.-M. Tang, and Y.-L. Wang, Reducing the height of independent spanning trees in chordal rings, IEEE Trans. Parallel Distrib. Syst., 18 (2007) 644–657.
[43] J.-S. Yang, J.-M. Chang, S.-M. Tang, and Y.-L. Wang, On the independent spanning trees of recursive circulant graphs G(cdm,d) with d > 2, Theoret. Comput. Sci., 410 (2009) 2001–2010.
[44] J.-S. Yang, J.-M. Chang, S.-M. Tang, and Y.-L. Wang, Constructing multiple independent spanning trees on recursive circulant graphs G(2m,2), Int. J. Found. Comput. Sci., 21 (2010) 73–90.
[45] J.-S. Yang, S.-M. Tang, J.-M. Chang, and Y.-L. Wang, Parallel construction of optimal independent spanning trees on hypercubes, Parallel Comput., 33 (2007) 73–79.
[46] M.-C. Yang, Constructing edge-disjoint spanning trees in twisted cubes Inform. Sci., 180 (2010) 4075–4083.
[47] M.-C. Yang, T.-K. Li, J.-M. Tan, L.-H. Hsu, On embedding cycles into faulty twisted cubes, Inform. Sci., 67 (2007) 205–214.
[48] M.-C. Yang, Edge-fault-tolerant node-pancyclicity of twisted cubes, Inform. Process. Lett., 109 (2009) 1206–1210.
[49] X. Yang, Q. Dong, E. Yang, J. Cao, Hamiltonian properties of twisted hypercube-like networks with more faulty elements, Theoret. Comput. Sci., 412 (2011) 2409–2417.
[50] A. Zehavi and A. Itai, Three tree-paths, J. Graph Theory, 13 (1989) 175–188.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊
 
系統版面圖檔 系統版面圖檔