臺灣博碩士論文加值系統

在網路的議題中，具有容錯性的廣播以及安全性的訊息分散皆擁有眾多應用。為了達到容錯及安全的需求，普遍的做法是以網路架構做為圖形結構，對其建構多棵擴展樹。我們將來源點當作樹根，複製k份的訊息，透過多棵擴展樹廣播至子結點，即可達到具有容錯性的廣播；另ㄧ方面，把訊息分割成k份，透過多棵擴展樹傳遞至子結點，便可達成安全訊息分散的目的。
一個圖形G的多棵擴展樹，如果有共同的樹根，而且它們兩兩之間任一點連接到樹根的路徑沒有使用共同的邊，則稱它們為一組邊互斥擴展樹。在最近的文獻中，Hsieh 和 Tu [Theoretical Computer Science 410 (2009) 926-932]提出一個能在n維局部扭轉超立方體上建構n棵邊互斥擴展樹的演算法，而局部扭轉超立方體是超立方體的變形。在本論文中，我們證明使用他們的演算法所建構出來的擴展樹其實為一組獨立擴展樹。換言之，任兩棵擁有共同樹根的擴展樹，任一點連接到樹根的路徑彼此為點互斥。

Fault-tolerant broadcasting and secure message distribution are important issues for numerous applications in networks. It is a common idea to design multiple spanning trees with a specific property in the underlying graph of a network to serve as a broadcasting scheme or a distribution protocol for receiving high levels of fault-tolerance and of security. The fault-tolerance can be achieved by sending k copies of the message and the security can be achieved by sending k parts of the message along the k spanning tree rooted at the source node. Recently, constructing multiple spanning trees of a given graph has received much attention.
A set of spanning trees in a graph G is said to be edge-disjoint if these trees are rooted at the same node without sharing any common edge. 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] recently presented an algorithm for constructing n edge-disjoint spanning trees in an n-dimensional locally twisted cube, which is a variant of the hypercube. In this thesis, we prove that indeed all spanning trees constructed by their algorithm are independent, i.e., any two spanning trees are rooted at the same node,say r, and for any other node v≠r, the two different paths from v to r, one path in each tree, are internally node-disjoint.

1 Introduction
1.1 Motivation and Intention
1.2 Outline
2 Interconnection Networks
2.1 HyperCubes
2.2 Locally Twisted Cubes
3 Independent spanning trees in locally twisted cubes
3.1 Constructing spanning trees in locally twisted cubes
3.2 Proof of the independency
4 Conclusion

[1] 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, pp. 472-478.
[2] 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 36 (2006) 607-610(in Chinese).
[3] 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 47 (2001) 73-86.
[4] 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.
[5] S. Curran, O. Lee and X. Yu, Finding four independent trees, SIAM Journal on Computing 35 (2006) 1023-1058.
[6] P. Fraigniaud and C.-T. Ho, Arc-disjoint spanning trees on the cube-connected-cyclesnetwork, in: Proc. of the International Conference on Parallel Processing, vol. 1, 1991,pp. 225-229.
[7] P. Fragopoulou, Edge-disjoint spanning trees on the star network with applications to fault tolerance, IEEE Transactions on Computers 45 (1996) 174-185.
[8] A. Huck, Independent Trees in Planar Graphs, Graphs and Combinatorics 15 (1999) 29-77.
[9] Z. Ge and S.L. Hakimi, Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs, SIAM Journal on Computing 26 (1997) 79-92.
[10] T. Hasunuma and H. Nagamochi, Independent spanning trees with small depths in iterated line digraphs, Discrete Applied Mathematics 110 (2001) 189-211.
[11] S.-Y. Hsieh and C.-J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoretical Computer Science 410 (2009) 926-932
[12] S.-Y. Hsieh and C.-Y. Wu, Edge-fault-tolerant Hamiltonicity of locally twisted cubes under conditional edge faults, Journal of Combinatorial Optimization 19 (2010) 16-30.
[13] K.S. Hu, S.-S. Yeoh, C. Chen and L.-H. Hsu, Node-pancyclicity and edge-pancyclicity of hypercube variants, Information Processing Letters 102 (2007) 1-7.
[14] A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation 79 (1988) 43-59.
[15] Y. Iwasaki, Y. Kajiwara, K. Obokata and Y. Igarashi, Independent spanning trees of chordal rings, Information Processing Letters 69 (1999) 155-160.
[16] S.L. Johnson and C.-T. Ho, Optimum broadcasting and personalized communication in hypercubes, IEEE Transactions on Computers 38 (1989) 1249-1268.
[17] C.-T. Lin, Embedding k(n-k) edge-disjoint spanning trees in arrangement graphs, Journal of Parallel and Distributed Computing 63 (2003) 1277-1287.
[18] Y.-J. Liu, W. Y. Chou, J. K. Lan and Chiuyuan Chen, Constructing independent spanning trees for hypercubes and locally twisted cubes, Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2009),Kaohsiung, Taiwan, (2009), pp. 17-22.
[19] M-J. Ma and J.-M. Xu, Panconnectivity of locally twisted cubes, Applied Mathematics Letters 19 (2006) 673-677.
[20] K. Obokata, Y. Iwasaki, F. Bao and Y. Igarashi, Independent spanning trees of product graphs and their construction, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E79-A (1996) 1894-1903.
[21] P. Ramanathan and K.G. Shin, Reliable broadcast in hypercube multicomputers,IEEE Transactions on Computers 37 (1988) 1654-1657.
[22] A.A. Rescigno, Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security, Information Sciences 137 (2001) 259-276.
[23] S.-M. Tang, Y.-L. Wang and Y.-H. Leu, Optimal independent spanning trees on hypercubes, Journal of Information Science and Engineering 20 (2004) 143-155.
[24] S.-M. Tang, J.-S. Yang, Y.-L. Wang and J.-M. Chang, Independent spanning trees on multidimensional torus networks, IEEE Transactions on Computers 59 (2010) 93-102.
[25] H. Yang and X. Yang, A fast diagnosis algorithm for locally twisted cube multiprocessor systems under the MM* model, Computers and Mathematics with Applications 53 (2007) 918-926.
[26] J.-S. Yang and J.-M. Chang, Independent spanning trees on folded hyper-stars, Networks, to appear.
[27] J.-S. Yang, J.-M. Chang and H.-C. Chan, Independent spanning trees on folded hypercubes, Proceedings of 10th International Symposium on Pervasive Systems, Algorithms, and Networks (I-SPAN 2009), Kaohsiung, Taiwan, (2009), pp. 73-83.
[28] 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 18 (2007) 644-657.
[29] J.-S. Yang, J.-M. Chang, S.-M. Tang and Y.-L. Wang, On the independent spanning trees of recursive circulant graphs G(cd^m; d) with d > 2, Theoretical Computer Science 410 (2009) 2001-2010.
[30] J.-S. Yang, J.-M. Chang, S.-M. Tang and Y.-L. Wang, Constructing multiple independent spanning trees on recursive circulant graphs G(2^m; 2), International Journal of Foundations of Computer Science 21 (2010) 73-90.
[31] J.-S. Yang, S.-M. Tang, J.-M. Chang and Y.-L.Wang, Parallel construction of optimal independent spanning trees on hypercubes, Parallel Computing 33 (2007) 73-79.
[32] X. Yang, G.M. Megson and D.J. Evans, Locally twisted cubes are 4-pancyclic, Applied Mathematics Letters 17 (2004) 919-925.
[33] X. Yang, D.J. Evans and G.M. Megson, The locally twisted cubes, International Journal of Computer Mathematics 82 (2005) 401-413.
[34] A. Zehavi and A. Itai, Three tree-paths, Journal of Graph Theory 13 (1989) 175-188.