臺灣博碩士論文加值系統

我們以LTQn 代表n 維度的局部扭轉立方體，謝孫源教授[S.-Y. Hsieh and C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science, 410 (2009) 926{932] 在2009 年提出一個在圖形LTQn 上，並 以"0"作為樹根，建構出n 個邊互斥的擴展樹之方法。接著在2010 年時，林嘉倩等作者[J.-C. Lin, J.-S. Yang, C.-C. Hsu, and J.-M. Chang, Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes, Information
Processing Letters, 110 (2010) 414{419] 證明了謝孫源教授的文章中所建構的擴展樹確實也是獨立擴展樹(以ISTs 簡稱)，換句話說，所有的擴展樹以相同的點作為樹根r，以及其餘的點v 與r 不相同，除了兩個端點v 與r 以外，在任兩棵樹上，由任意點v 到樹根r 的路徑中所有的點都不重複，我們可以稱這是一組獨立擴展樹。但是，在不久之後，Liu 等作者在2011 年的文章[Y.-J. Liu, J.-K. Lan, W.-Y. Chou, and C. Chen, Constructing independent spanning trees for locally twisted cubes, Theoretical Computer Science, 412 (2011) 2237{2252] 指出在維度4 以上的局部扭轉立方體沒有點對稱的性質，並提出一個在圖形LTQn 上以任意點作為樹根，建構n 個獨立擴展樹的方法。雖然此方法可以平行的方式同時建構n 個獨立擴展樹，但是不能同時以完全平行方式建構每棵擴展樹，在這篇文章裡，我們重新審視在圖形LTQn 上，並以任意點當作樹根，建構n 個獨立擴展樹的問題。因此，我們提出一個完全平行的演算法，此方法是將謝孫源教授的演算法作稍微的修改。

Let LTQn denote the n-dimensional locally twisted cube. Hsieh and Tu [S.-Y. Hsieh and C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science, 410 (2009) 926{932] presented an algorithm to construct n edge-disjoint spanning trees rooted at vertex 0 in LTQn. Later on, Lin et al. [J.-C. Lin, J.-S. Yang, C.-C. Hsu, and J.-M. Chang, Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes, Information Processing Letters, 110 (2010) 414{419] proved that Hsieh and Tu's spanning trees are indeed independent spanning trees (ISTs for short), i.e., all spanning trees are rooted at the same vertex r and for any other vertex v(≠ r), the paths from v to r in any two trees are vertex-disjoint except the two end vertices v and r. Shortly afterwards, Liu et al. [Y.-J. Liu, J.-K. Lan, W.-Y. Chou, and C. Chen, Constructing independent spanning trees for locally twisted cubes, Theoretical Computer Science, 412 (2011) 2237{2252] pointed out that LTQn fails to be vertex-transitive for n ≥ 4
and proposed an algorithm for constructing n ISTs rooted at an arbitrary vertex of LTQn. Although this algorithm can simultaneously construct n ISTs in parallel, it is not fully parallelized for the construction of each spanning tree. In this paper, we revisit the problem of constructing n ISTs rooted at an arbitrary vertex of LTQn. As a consequence, we present a fully parallelized approach that is obtained from Hsieh and Tu's algorithm with a slight modication.

摘要 I
Abstract II
誌謝 III
Contents IV
List of Tables VI
List of Figures VIII
1 Introduction 1
1.1 Outline of the Thesis 3
2 Interconnection Networks 4
2.1 Hypercubes 5
2.2 Locally twisted cubes 7
3 Related Work 9
4 Main Result 11
4.1 Constructing ISTs on LTQn in parallel 11
4.2 Correctness 16
5 Conclusion and Future Works 31
5.1 Conclusion 31
5.2 Future Works 32
Bibliography 33

[1] S. Abraham and K. Padmanabhan, The twisted cube topology for multiprocessors: 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 997, pp. 472-478.
[3] P. Cull and S.M. Larson, The Mobius cubes, IEEE Trans. Comput., 44 (1995) 647-659.
[4] Q.-Y. Chang, M.-J. Ma, and J.-M. Xu, Fault-tolerant pancyclicity of locally twisted cubes (in Chinese), J. China Univ. Sci. Tech., 36 (2006) 607-610.
[5] X.-B. Chen, Parallel construction of optimal independent spanning trees on Cartesian product of complete graphs, Inform. Process. Lett., 111 (2011) 235-238.
[6] B. Cheng, J. Fan, X. Jia, and J. Jia, Parallel construction of independent spanning trees and an application in diagnosis on Mobius cubes, J. Supercomput., 65 (2013) 1279-1301.
[7] 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.
[8] B. Cheng, J. Fan, X. Jia, and S. Zhang, Independent spanning trees in crossed cubes, Inform. Sci., 233 (2013) 276-289.
[9] B. Cheng, J. Fan, X. Jia, S. Zhang, and B. Chen, Constructive algorithm of independent spanning trees on Mobius cubes, Comput. J., 56 (2013) 1347-1362.
[10] J. Cheriyan and S.N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. J. Algorithms, 9 (1988) 507-537.
[11] S. Curran, O. Lee, and X. Yu, Finding four independent trees. SIAM J. Comput., 35 (2006) 1023-1058.
[12] Z. Ge and S.L. Hakimi, Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs, SIAM J. Comput., 26 (1997) 79-92.
[13] Y. Han, J. Fan, S. Zhang, J. Yang, and P. Qjan, Embedding meshes into locally twisted cubes, Inform. Sci., 180 (2010) 3794-3805.
[14] T. Hasunuma and H. Nagamochi, Independent spanning trees with small depths in iterated line graphs, Discrete Appl. Math., 110 (2001) 189-211.
[15] S.-Y. Hsieh and C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoret. Comput. Sci., 410 (2009) 926-932.
[16] S.-Y. Hsieh and C.-Y. Wu, Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults, J. Combin. Optim. 19 (2010) 16-30.
[17] K.S. Hu, S.-S. Yeoh, C. Chen, and L.-H. Hsu, Node-pancyclicity and edgepancyclicity of hypercube variants, Inform. Process. Lett., 102 (2007) 1-7.
[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. Huck, Independent branching in acyclic digraphs, Discrete Math, 199 (1999) 245-249.
[21] A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Inform. Comput., 79 (1988) 43-59.
[22] Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, Independent spanning trees of chordal rings, Inform. Process. Lett., 69 (1999) 155-160.
[23] J.-S. Kim, H.-O. Lee, E. Cheng, and L. Liptak, Optimal independent spanning trees on odd graphs, J. Supercomputing, 56 (2011) 212-225.
[24] J.-S. Kim, H.-O. Lee, E. Cheng, and L. Liptak, Independent spanning trees on even networks, Inform. Sci., 181 (2011) 2892-2905.
[25] P.D. Kulasinghe and S. Bettayeb, Multiply-twisted hypercube with 5 or more dimensions is not vertex transitive, Inform. Process. Lett., 53 (1995) 33-36.
[26] J.-C. Lin, J.-S. Yang, C.-C. Hsu, and J.-M. Chang, Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes, Inform. Process. Lett., 110 (2010) 414-419.
[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] M.-J. Ma and J.-M. Xu, Panconnectivity of locally twisted cubes, Appl. Math. Lett., 19 (2006) 673-677.
[29] M.-J. Ma and J.-M. Xu, Weak Edge-pancyclicity of locally twisted cubes, Ars Combin., 89 (2008) 89-94.
[30] 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.
[31] S. Nagai and S. Nakano, A linear-time algorithm to nd independent spanning trees in maximal planar graphs, IEICE Trans. Fund. Electron. Comm. Comput. Sci., E84-A (2001) 1102-1109.
[32] 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.
[33] J.-H. Park, H.-S. Lim, and H.-C. Kim, Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theoret. Comput. Sci., 377 (2007) 170-180.
[34] A.A. Rescigno, Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security, Inform. Sci., 137 (2001) 259-276.
[35] Y. Saad and M.H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput., 37 (1988) 867-872.
[36] S.-M. Tang, Y.-L. Wang, and Y.-H. Leu, Optimal independent spanning trees on hypercubes, J. Inform. Sci. Eng., 20 (2004) 143-155.
[37] 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.
[38] Y. Wang, J. Fan, G. Zhou, and X. Jia, Independent spanning trees on twisted cubes, J. Parallel Distrib. Comput., 72 (2012) 58-69.
[39] 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.
[40] J. Werapun, S. Intakosum, and V. Boonjing, An ecient parallel construction of optimal independent spanning trees on hypercubes, J. Parallel Distrib. Comput., 72 (2012) 1713-1724.
[41] R.W. Whitty, Vertex-disjoint paths and edge-disjoint branchings in directed graphs, J. Graph Theory, 11 (1987) 349-358.
[42] X. Xu, W. Zhai, J.-M. Xu, A. Deng, and Y. Yang, Fault-tolerant edgepancyclicity of locally twisted cubes Inform. Sci., 181 (2011) 2268-2277.
[43] H. Yang and X. Yang, A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM model, Comput. Math. Appl., 53 (2007) 918-926.
[44] 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.
[45] J.-S. Yang and J.-M. Chang, Independent spanning trees on folded hyper-stars, Networks, 56 (2010) 272-281.
[46] J.-S. Yang and J.-M. Chang, Optimal independent spanning trees on Cartesian product of hybrid graphs, Comput. J., 57 (2014) 93-99.
[47] 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.
[48] 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.
[49] 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.
[50] 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.
[51] X. Yang, G.M. Megson, and D.J. Evans, Locally twisted cubes are 4-pancyclic, Appl. Math. Lett., 17 (2004) 919-925.
[52] X. Yang, D.J. Evans, and G.M. Megson, The locally twisted cubes, Int. J. Comput. Math., 82 (2005) 401-413.
[53] A. Zehavi and A. Itai, Three tree-paths, J. Graph Theory, 13 (1989) 175-188.