對於一圖G的生成樹所構成的集合，如果這些生成樹都有著共通的根節點r，並且對於所有G中的節點v，所有由v至r的路徑都滿足內部結點不相交和邊不相交，則該集合被稱為G的獨立生成樹。建構獨立生成樹目前已經被應用在許多場合，例如在可靠網路中傳遞安全訊息以及容錯問題等。焦煎餅圖屬於凱萊圖的子圖，而凱萊圖也被廣泛運用在現今常見的網路結構中。在這篇論文中，將會提出建構焦煎餅圖的最大獨立生成樹集的演算法，並證明演算法的正確性。

The construction of independent spanning trees has practical applications in many
domains, such as secure message distribution and fault tolerance in reliable communication networks. This study proposes an e ective algorithm for improving connections
between networks in a speci c topology, doing so by constructing independent spanning
trees. The set of the spanning trees of a graph G is called independent spanning trees if
(1) these spanning trees have a common root r, and (2) for each vertex v in G{r}, the
paths from v to r are vertex-disjoint and edge-disjoint. A burnt pancake network is a type
of Cayley graph, which has been extensively applied in present-day network structures.
Herein, we rst expand the target to construct maximal independent spanning trees on
a burnt pancake network in O(N x n), where N is the number of nodes of BPn and n
is the length of the indices of each node. Subsequently, we prove the e ectiveness of our
proposed algorithm in constructing independent spanning trees.

[1] F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi, ”Reliable broadcasting and securedistributing in channel networks,” in:Proc. of 3rd International Symposium on Par-allel Architectures, Algorithms and Networks, ISPAN’97, Taipei, December 1997, pp.472-478.
[2] S. A. Blanco, C. Buehrle, A. Patidar, ”Cycles in the burnt pancake graph,” DiscreteApplied Mathematics, vol. 271, pp. 1-14, 2019
[3] J.M. Chang, T.J.Yang, and J.S. Yang, ”A parallel algorithm for constructing inde-pendent spanning trees in twisted cubes” Discrete Applied Mathematics, vol. 219,Pages 74-82, 2017
[4] Y.H. Chang, J.S. Yang, S.Y. Hsieh, J.M. Chang, and Y.L. Wang ”Construction inde-pendent spanning trees on locally twisted cubes in parallel,”Journal of CombinatorialOptimization, vol. 33, pp. 956-967, 2017.
[5] D. Cheng, C. Chan and S. Hsieh, ”Constructing Independent Spanning Trees onPancake Networks,” in IEEE Access, vol. 8, pp. 3427-3433, 2020
[6] J. Cheriyan, and S. N. Maheshwari, ”Finding nonseparating induced cycles and in-dependent spanning trees in 3-connected graphs,”Journal of Algorithms, vol. 9, no.4, pp. 507-537, 1988.
[7] S. Curran, O. Lee, and X.X. Yu, ”Finding four independent trees,”SIAM Journalon Computing, vol. 35, no. 5, pp. 1023-1058, 2006.
[8] W. H. Gates, C. H. Papadimitriou, ”Bounds for sorting by prefix reversal,” DiscreteMathematics, vol 27, pp. 47-57, 1979
[9] A. Itai, and M. Rodeh, ”The multi-tree approach to reliability in distributed net-works,”.Information and Computation, vol. 79, no. 1, pp. 43-59, 1988.
[10] S.S. Kao, J.M. Chang, K.J. Pai, and R.Y. Wu, ”Constructing Independent SpanningTrees on Bubble-Sort Networks,” in:International Computing and CombinatoricsConference, COCOON2018, vol 10976, pp 1-13, 2018
[11] S.S. Kao, K.J. Pai, S.Y. Hsieh, R.Y. Wu, and J.M. Chang, ”Amortized efficiency ofconstructing multiple independent spanning trees on bubble-sort networks,”Journalof Combinatorial Optimization, vol. 38, no. 3, pp. 972-986, 2019.
[12] A.A. Rescigno, ”Vertex-Disjoint Spanning Trees of the Star Network with Applica-tions to Fault-Tolerance and Security,”Information Sciences, vol. 137, pp. 259-276,2001.
[13] J.S. Yanga, H.C. Chan, and J.M. Chang, ”Broadcasting secure messages via optimalindependent spanning trees in folded hypercubes,”Discrete Applied Mathematics,vol. 159, no. 12, pp. 1254-1263, 2011.
[14] A. Zehavi, and A. Itai, ”Three tree-paths,”Journal of Graph Theory, vol. 13, no. 2,pp. 175-188, 1989.