在圖G中，有一個生成樹集合，樹根皆為同一點 r ，對於所有非r的點v，在每棵生成樹從r到v的路徑上不經過重複的點(除了r與v之外)，則這群生成樹稱為獨立生成樹。獨立生成樹可應用於很多領域，包括：容錯廣播及機密訊息傳遞。交替群組網路AN_n (n代表維度)是凱萊圖的的一種，也是(n,k)-星圖的一種特例，AN_n和(n,n-2)-星圖是同構的。(n,k)-星圖S_{n,k}是星狀網路的一般化。到目前為止，在交替群組網路與(n,k)-星圖建構獨立生成樹的方法還未被提出，在本論文中，對於交替群組網路與(n,k)-星圖，我們分別提出遞迴與平行的建構方法。交替群組網路上，遞迴演算法主要想法為從小樹建構到大樹、使用三角形廣度優先搜尋建構獨立生成樹骨架、使用廣度優先搜尋連結剩餘的點，另一方面，平行演算法主要想法為使用三角形廣度優先搜尋平行地建構所有獨立生成樹骨架，使用規則平行地連結所有剩餘的點。(n,k)-星圖上，遞迴演算法主要想法為從小樹建構到大樹、使用修改的廣度優先搜尋建構獨立生成樹骨架、使用廣度優先搜尋連結剩餘的點，另一方面，平行演算法主要想法為使用修改的廣度優先搜尋平行建構所有獨立生成樹骨架，使用規則平行地連結剩餘的點。我們也驗證遞迴與平行演算法在交替群組網路與(n,k)-星圖的正確性。在交替群組網路上，遞迴演算法時間複雜度是 O(n x n!)，其中 n!是AN_n點數的兩倍， 另一方面，如果有n-1顆處理器平行運算，則平行演算法時間複雜度可降為O(n!)。在(n,k)-星圖上， 遞迴演算法時間複雜度是O(n x frac{n!}{(n-k)!})，其中frac{n!}{(n-k)!}是S_{n,k}點數，另一方面，如果有n-1顆處理器平行運算，則平行演算法時間複雜度可降為O(frac{n!}{(n-k)!})。兩種演算法在交替群組網路與(n,k)-星圖都是正確的且時間複雜度如前述。 更進一步來看，在交替群組網路與(n,k)-星圖，平行演算法比遞迴演算法更有效率。

A set of spanning trees in a graph G is called independent spanning trees (ISTs) if they are rooted at the same vertex, say r, and for each vertex v(
e r) in G, the two paths from r to v in any two trees share no common vertex expect for r and v. ISTs can be applied in a lot of fields, such as fault-tolerant broadcasting and secure message distribution. The alternating group network AN_n (where n stands for the dimension) is a subclass of Cayley graphs. Alternating group networks constitute a special case of (n,k)-star graphs. AN_n is isomorphic to an (n,n-2)-star graph. The (n,k)-star graph S_{n,k} is a generalized version of the star networks. The methods of constructing ISTs on alternating group networks and (n,k)-star graphs are still unknown. In this thesis, we propose a recursive algorithm and a parallel algorithm of constructing ISTs on alternating group networks and (n,k)-star graphs. The main ideas of the recursive algorithm on AN_n are to use induction to develop small trees to big trees, to use a triangle breadth-first search (TBFS) process to create a backbone of an IST, and to use breadth-first search (BFS) process to connect the rest of nodes, while the main ideas of the parallel algorithm on AN_n are to create backbones through TBFS processes in parallel, and to use the specific rules to connect the rest of nodes in parallel. On the other hand, the main ideas of the recursive algorithm on S_{n,k} are to use induction to develop small trees to big trees, to use a modified breadth-first search (MBFS) process to create a backbone of an IST, and to use breadth-first search (BFS) process to connect the rest of nodes, while the main ideas of the parallel algorithm on S_{n,k} are to create backbones through MBFS processes in parallel, and to use the specific rules to connect the rest of nodes in parallel. We also present the validation of both algorithms on AN_n and S_{n,k}. The time complexity of the recursive algorithm on AN_n is O(n x n!), where n! is twice the number of nodes of AN_n, while the time complexity of the parallel algorithm on AN_n can be reduced to O(n!) if there are n-1 processors computing in parallel. On the other hand, the time complexity of the recursive algorithm on S_{n,k} is O(n x frac{n!}{(n-k)!}), where frac{n!}{(n-k)!} is the number of nodes of S_{n,k}, while the time complexity of the parallel algorithm on S_{n,k} can be reduced to O(frac{n!}{(n-k)!}) if there are n-1 processors computing in parallel. Both algorithms on AN_n and S_{n,k} are correct with the stated time complexity. Furthermore, the parallel algorithms are more efficient than the recursive algorithms on AN_n and S_{n,k}.

[1] S.B. Akers and B. Krishnamurthy, "A Group-Theoretic Model for Symmetric Interconnection Networks," IEEE Trans. Computers, vol. 38 (1989), pp. 555-566.
[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, pp. 472-478.
[3] J.H. Chang, and J. Kim, "Ring Embedding in Faulty (n; k)-Star Graphs," Proceedings Eighth International Conference on Parallel and Distributed Systems. ICPADS 2001, pp. 99-106, 2001.
[4] Y.H. Chang, J.S. Yang, J.M. Chang, and Y.L. Wang "A Fast Parallel Algorithm for Constructing Independent Spanning Trees on Parity Cubes," Applied Mathematics
and Computation vol. 268, pp. 489-495, 2015.
[5] Y.H. Chang, J.S. Yang, S.Y. Hsieh, J.M. Chang, and Y.L. Wang "Construction independent spanning trees on locally twisted cubes in parallel," Journal of Combinatorial Optimization, vol. 33, pp. 956-967, 2017.
[6] J.M. Chang, T.J. Yang, and J.S. Yang, "A parallel algorithm for constructing independent spanning trees in twisted cubes," Discrete Applied Mathematics, vol. 219,
pp. 74-82, 2017.
[7] Y.S. Chen, and K.S. Tai, "A near-optimal broadcasting in (n,k)-star graphs," in: Proc. ACIS Int. Conf. on Software Engineering Applied to Networking and Parallel
Distributed Computing, pp. 217-224, 2000.
[8] B. Chen, W. Xiao, and B. Parhami, "Internode Distance and Optimal Routing in a Class of Alternating Group Networks," IEEE Transactions on Computers, vol. 55,
no. 12 (2006), pp. 1645-1648.
[9] B.L Cheng, J.X. Fan, X.H. Jia, and S.K. Zhang, "Independent spanning trees in crossed cubes," Information Sciences, vol. 233, pp. 276-289, 2013.
[10] B.L. Cheng, J.X. Fan, X.H. Jia, S.K. Zhang, and B.R. Chen, "Constructive Algorithm of Independent Spanning Trees on Mobius Cubes," The Computer Journal, vol. 56,
no. 11, pp. 1347-1362, 2013.
[11] E. Cheng, K. Qiu, and Z. Shen, "A Note on the Alternating Group Network," Supercomputing, vol. 59, no. 1, pp. 246-248, 2012.
[12] J. Cheriyan, and S. N. Maheshwari, "Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs," Journal of Algorithms, vol. 9, no. 4, pp. 507-537, 1988.
[13] W.K. Chiang, and R.J. Chen, "The (n,k)-Star Graph: A Generalized Star Graph," Information Processing Letters, vol. 56, no. 5, pp. 259-264, 1995.
[14] W.K. Chiang, and R.J. Chen, "Topological Properties of the (n,k)-Star Graph," International Journal of Foundations of Computer Science, vol. 9, no. 2, pp. 235-
248, 1998.
[15] S. Curran, O. Lee, and X.X. Yu, "Finding four independent trees," SIAM Journal on Computing, vol. 35, no. 5, pp. 1023-1058, 2006.
[16] Y.O. Hamidoune, A.S. Llado, and O. Serra, "The Connectivity of Hierarchical Cayley Digraphs," Discrete Applied Mathematics, vols. 37-38 (1992), pp. 275-280.
[17] S.Y. Hsieh and C.J. Tu, "Constructing edge-disjoint spanning trees in locally twisted cubes," Theoretical Computer Science, vol. 410, pp. 926-932, 2009.
[18] H.C. Hsu, Y.L. Hsieh, J.M. Tan, L.H. Hsu, "Fault Hamiltonicity and Fault Hamiltonian Connectivity of the (n,k)-Star Graphs," Networks, vol. 42, pp. 189-201, 2003.
[19] H.C. Hsu, C.K. Lin, H.M. Hung, and L.H. Hsu, "The Spanning Connectivity of the (n,k)-Star Graphs," International Journal of Foundations of Computer Science, vol. 17, pp. 415-434, 2006.
[20] Z. Hussain, B. AlBdaiwi, and A. Cerny "Node-independent spanning trees in Gaussian networks," Journal of Parallel and Distributed Computing, vol. 109, pp 324-332, 2017.
[21] A. Itai, and M. Rodeh, "The multi-tree approach to reliability in distributed networks,". Information and Computation, vol. 79, no. 1, pp. 43-59, 1988.
[22] Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi, "Independent spanning trees of chordal rings," Information Processing Letters, vol. 69, no. 3, pp. 155-160, 1999.
[23] J.S. Jwo, S. Lakshmivarahan, and S.K. Dhall, "A New Class of Interconnection Networks Based on the Alternating Groups," Networks, vol. 23 (1993), pp. 315-326.
[24] S.S. Kao, J.M. Chang, K.J. Pai, J.S. Yang, S.M. Tang, and R.Y. Wu, "A parallel construction of vertex-disjoint spanning trees with optimal heights in star networks," in: International Conference on Combinatorial Optimization and Applications, COCOA2017, vol. 10627, pp. 41-55, 2017, Springer, Cham.
[25] S.S. Kao, J.M. Chang, K.J. Pai, and R.Y. Wu, "Constructing Independent Spanning Trees on Bubble-Sort Networks," in: International Computing and Combinatorics Conference, COCOON2018, vol 10976, 2018, pp 1-13, Springer, Cham.
[26] S.S. Kao, K.J. Pai, S.Y. Hsieh, R.Y. Wu, and J.M. Chang, "Amortized e ciency of constructing multiple independent spanning trees on bubble-sort networks," Journal of Combinatorial Optimization, vol. 38, no. 3, pp. 972-986, 2019.
[27] S. Lakshmivarahan, J.S. Jwo, and S.K. Dhall, "Symmetry in Interconnection Networks Based on Cayley Graphs of Permutations: A Survey," Parallel Computing, vol. 19 (1993), pp. 361-407.
[28] T.C. Lin, and D.R. Duh, "The Spanning Connectivity of the (n,k)-Star Graphs," International Journal of Foundations of Computer Science, vol. 17, pp. 415-434, 2006.
[29] Y.J. Liu, J.K. Lan, W.Y. Chou, and C. Chen, "Constructing independent spanning trees for locally twisted cubes," Theoretical Computer Science, vol. 412, pp. 2237-2252, 2011.
[30] A.A. Rescigno, "Vertex-Disjoint Spanning Trees of the Star Network with Applications to Fault-Tolerance and Security," Information Sciences, vol. 137, pp. 259-276, 2001.
[31] 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.
[32] Y. Wang, J.X. Fan, X.H. Jia, and H. Huang "An algorithm to construct independent spanning trees on parity cubes," Theoretical Computer Science, vol. 465, pp. 61-72, 2012.
[33] Y. Wang, J.X. Fan, G.D. Zhou, and X.H. Jia "Independent spanning trees on twisted cubes," Journal of Parallel and Distributed Computing, vol. 72, pp. 58-69, 2012.
[34] J. Werapun, S. Intakosum, and V. Boonjing "An e cient parallel construction of optimal independent spanning trees on hypercubes," Journal of Parallel and Distributed Computing, vol. 72, no. 12, pp 1713-1724, 2012.
[35] J.S. Yang, J.M. Chang, S.M. Tang, and Y.L. Wang, "Parallel Construction of Optimal Independent Spanning Trees on Hypercubes," Parallel Computing, vol. 33 , pp. 73-79, 2007.
[36] J.S. Yang, J.M. Chang, S.M. Tang, and Y.L. Wang, "On the independent spanning trees of recursive circulant graphs with G(cdm; d) with d > 2," Theoretical Computer Science, vol. 410, pp. 2001-2010, 2009.
[37] J.S. Yang, H.C. Chan, and J.M. Chang, "Broadcasting secure messages via optimal independent spanning trees in folded hypercubes," Discrete Applied Mathematics, vol. 159, no. 12, pp. 1254-1263, 2011.
[38] J. Youhu, "A New Class of Cayley Networks Based on the Alternating Groups," Applied Mathematics-JCU, vol. 14(A), no. 2 (1998), pp. 235-239, in Chinese.
[39] A. Zehavi, and A. Itai, "Three tree-paths," Journal of Graph Theory, vol. 13, no. 2, pp. 175-188, 1989.
[40] S. Zhou, W. Xiao, and B. Parhami, "Construction of Vertex-Disjoint Paths in Alternating Group Networks," Supercomputing, vol. 54, no. 2 (2010), pp. 206-228.