廣義遞迴環形圖可以被廣泛的應用在互聯網路方面的設計，包括了計算機架構中多處理器之間的點對點互相通訊。獨立生成樹為一群以相同節點為根節點的生成樹，而且除了此點外任一點到根節點的路徑互不相交。因為此特性，獨立生成樹被大量的用在容錯性的加強以及訊息安全的傳播上。在這篇論文裡，我們提出一個新的方法來建構在廣義遞迴環形上的獨立生成樹。對於這個圖上的每一點，首先透過最短路徑的演算法找出需要的路由方向，以此並根據所屬的生成樹來計算出父節點，最後藉由求出的每個點對應的父節點來建構出在廣義遞迴環形圖上的最大獨立生成樹。我們提出的方法時間複雜度為O(Nh)，其中，N代表節點數，h為該圖的維度。這個方法用來解決之前應用在建構遞迴環形圖的獨立生成樹演算法限制因而擴展到點數量更彈性的廣義遞迴環形圖上。要尋找並建構獨立生成樹為一個有挑戰性的研究，我們期待提出的在廣義遞迴環形圖建構獨立生成數樹方法可以在互聯網路的容錯或是訊息傳播安全上的設計有所應用。

The generalized recursive circulant networking can be widely used in the design and implementation of interconnection networks. It consists of multi-processors, each is connected through bidirectional, point-to-point communication channels to different neighbors. A set of spanning trees are said to be independent if they are rooted at the same vertex and for each of the remaining vertex there exists internally disjoint paths connected to the root. Independent spanning trees(ISTs) are largely used to improve fault-tolerant ability and secure information distribution. In this work, we proposed a novel method to construct independent spanning trees on generalized recursive circulant graphs(GRC graphs). On each vertex, we first apply the shortest path routing concept to collect the needed movements which indicate a connection from a node to another one. Then finding the vertex’s parents through the strategy depends on the IST we select. Eventually, the strategy leads to forming multiple internally disjoint paths from the vertex to the root. The proposed method can construct maximal ISTs on GRC graphs in O(Nh) time complexity, where N, h denotes cardinality and dimension of the graphs. Also, it loosened the restricted conditions in previous research and extended the result to a more general vertex setting as generalized recursive circulant graphs. Searching independent spanning trees is a challenging problem. We look forward to our results can be widely used in an interconnection network to enhance its fault-tolerant property or achieve reliable broadcasting and design secure distributed protocols.

[1] B. Alspach, S. C. Locke, and D. Witte, “The hamilton spaces of cayley graphs on abelian groups,” Discrete mathematics, vol. 82, no. 2, pp. 113–126, 1990.

[2] F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi, “Reliable broadcasting and secure distributing in channel networks,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. 81, no. 5, pp. 796–806, 1998.

[3] J.-C. Bermond, F. Comellas, and D. F. Hsu, “Distributed loop computer-networks: a survey,” Journal of parallel and distributed computing, vol. 24, no. 1, pp. 2–10, 1995.

[4] F. T. Boesch and A. P. Felzer, “A general class of invulnerable graphs,” Networks, vol. 2, no. 3, pp. 261–283, 1972.

[5] F. Boesch and R. Tindell, “Circulants and their connectivities,” Journal of Graph Theory, vol. 8, no. 4, pp. 487–499, 1984.

[6] B. Cheng, D. Wang, and J. Fan, “Constructing completely independent spanning trees in crossed cubes,” Discrete Applied Mathematics, vol. 219, pp. 100–109, 2017.

[7] D.-W. Cheng, C.-T. Chan, and S.-Y. Hsieh, “Constructing independent spanning trees on pancake networks,” IEEE Access, vol. 8, pp. 3427–3433, 2019.

[8] B. Elspas and J. Turner, “Graphs with circulant adjacency matrices,” Journal of Combinatorial Theory, vol. 9, no. 3, pp. 297–307, 1970.

[9] R. C. Entringer, D. E. Jackson, and D. Snyder, “Distance in graphs,” Czechoslovak Mathematical Journal, vol. 26, no. 2, pp. 283–296, 1976.

[10] J.-F. Huang, S.-S. Kao, S.-Y. Hsieh, and R. Klasing, “Top-down construction of independent spanning trees in alternating group networks,” IEEE Access, vol. 8, pp. 112 333–112 347, 2020.

[11] 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.

[12] S.-S. Kao, K.-J. Pai, S.-Y. Hsieh, R.-Y. Wu, and J.-M. Chang, “Amortized efficiency of constructing multiple independent spanning trees on bubble-sort networks,” Journal of Combinatorial Optimization, vol. 38, no. 3, pp. 972–986, 2019.

[13] F. T. Leighton, Introduction to parallel algorithms and architectures: Arrays· trees· hypercubes. Elsevier, 2014.

[14] C.-F. Lin, J.-F. Huang, and S.-Y. Hsieh, “Constructing independent spanning trees on transposition networks,” IEEE Access, vol. 8, pp. 147 122–147 132, 2020.

[15] B. Mans, “Optimal distributed algorithms in unlabeled tori and chordal rings,” Journal of Parallel and Distributed Computing, vol. 46, no. 1, pp. 80–90, 1997.

[16] M. E. Muzychuk, M. H. Klin, and R. P¨oschel, “The isomorphism problem for circulant graphs via schur ring theory.” Codes and association schemes, vol. 56, pp. 241–264, 1999.

[17] A. A. Rescigno, “Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security,” Information Sciences, vol. 137, no. 1-4, pp. 259–276, 2001.

[18] S.-M. Tang, Y.-L. Wang, and C.-Y. Li, “Generalized recursive circulant graphs,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 1, pp. 87–93, 2011.

[19] 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.

[20] 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,” Theoretical Computer Science, vol. 410, no. 21-23, pp. 2001–2010, 2009.

[21] A. Zehavi and A. Itai, “Three tree-paths,” Journal of Graph Theory, vol. 13, no. 2, pp. 175–188, 1989.