在互連網路使用邊互斥生成樹對於資料擴散及傳播問題上提供了幾個優點，其中包含頻寬的增加及容錯增大等等。在這篇論文中，我們是第一個說明如何在局部雙扭超方體上去嵌入多顆邊互斥生成樹的相關問題，並且主要研究目標是使其能夠平行建構及數量為最多顆的生成樹。而主要的基本概念，是建構在所謂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.

[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obius 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.