在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.