臺灣博碩士論文加值系統

在給定任意圖G，獨立生成樹就是生成樹的集合，所有的獨立生成樹都擁有相同的根結點，在不同的獨立生成樹中，從根結點到相同的節點的所有路徑都是內部結點不相交和邊不相交，在一個圖上建構多個獨立生成樹有很多種應用方式，例如:容錯廣播和發送安全訊息，煎餅圖是凱萊圖的子圖，同時因為凱萊圖在設計互連網絡是很重要的，所以在這種圖上建立獨立生成樹會有很多應用方式，在這篇論文，我們提出演算法來建立獨立生成樹在煎餅圖上，也會檢驗演算法的運作在不同維度的煎餅圖上，最後我們會證明演算法的正確性。

For any graph G, the set of independent spanning trees (ISTs) is defined as the set of spanning trees in $G$. All ISTs have the same root, paths from the root to another vertex between distinct trees are vertex-disjoint and edge-disjoint. The construction of multiple independent trees on a graph has numerous applications, such as fault-tolerant broadcasting and secure message distribution. The pancake graph is a subclass of Cayley graphs and since Cayley graphs are crucial for designing interconnection networks, constructing ISTs on these graphs is necessary for many practical applications. In this paper, we propose algorithms for constructing ISTs on pancake graph. Examining the use of our algorithm for constructing ISTs on pancake graph in different dimensions. We also present proofs about the construction of ISTs on pancake graph to verify that the correctness of these algorithms.

1 Introduction 1
2 Preliminaries 4
3 Algorithm of ISTs 6
3.1 Main Algorithm 9
3.2 Algorithm 2 14
3.3 Algorithm 3 19
4 Proof Regarding Algorithms 24
5 Conclusion 28
Bibliography 29

[1] Akl, S. G., Qiu, K., and Stojmenović, I. (1993). Fundamental algorithms for the star and pancake interconnection networks with applications to computational geometry. Networks, 23(4), 215-225.
[2] Bao, F., Funyu, Y., Hamada, Y., and Igarashi, Y. (1998). Reliable broadcasting and secure distributing in channel networks. IEICE Transactions on Fundamentals
of Electronics, Communications and Computer Sciences, 81(5), 796-806.
[3] Bass, D. W., and Sudborough, I. H. (2003). Pancake problems with restricted prefix reversals and some corresponding cayley networks. Journal of Parallel and Distributed Computing, 63(3), 327-336.
[4] Berthomé, P., Ferreira, A., and Pérennès, S. (1996). Optimal information dissemination in star and pancake networks. IEEE Transactions on Parallel and Distributed
Systems, 7(12), 1292-1300.
[5] Chang, J. M., Yang, T. J., and Yang, J. S. (2017). A parallel algorithm for constructing independent spanning trees in twisted cubes. Discrete Applied Mathematics, 219, 74-82.
[6] Chang, Y. H., Yang, J. S., Hsieh, S. Y., Chang, J. M., and Wang, Y. L. (2017). Construction independent spanning trees on locally twisted cubes in parallel. Journal of Combinatorial Optimization, 33(3), 956-967.
[7] Cheriyan, J., and Maheshwari, S. N. (1988). Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs. Journal of Algorithms, 9(4), 507-537.
[8] Curran, S., Lee, O., and Yu, X. (2006). Finding four independent trees. SIAM Journal on Computing, 35(5), 1023-1058.
[9] Itai, A., and Rodeh, M. (1988). The multi-tree approach to reliability in distributed networks. Information and Computation, 79(1), 43-59.
[10] Kaneko, K., and Peng, S. (2006, December). Disjoint paths routing in pancake graphs. In 2006 Seventh International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT’06) (pp. 254-259). IEEE.
[11] Kao, S. S., Pai, K. J., Hsieh, S. Y., Wu, R. Y., and Chang, J. M. (2019). Amortized efficiency of constructing multiple independent spanning trees on bubble-sort
networks. Journal of Combinatorial Optimization, 1-15.
[12] Kao, S. S., Chang, J. M., Pai, K. J., and Wu, R. Y. (2018, July). Constructing Independent Spanning Trees on Bubble-Sort Networks. In International Computing
and Combinatorics Conference (pp. 1-13). Springer, Cham.
[13] Kao, S. S., Chang, J. M., Pai, K. J., Yang, J. S., Tang, S. M., and Wu, R. Y. (2017, December). A parallel construction of vertex-disjoint spanning trees with optimal heights in star networks. In International Conference on Combinatorial Optimization and Applications (pp. 41-55). Springer, Cham.
[14] Nguyen, Q. T., and Bettayeb, S. (2011). On the genus of pancake network. Int. Arab J. Inf. Technol., 8(3), 289-292.
[15] Quinn, M. J. (1994). Parallel computing: theory and practice. McGrawHill, Inc..
[16] Rescigno, A. A. (2001). Vertex-disjoint spanning trees of the star network with applications to fault-tolerance and security. Information Sciences, 137(1-4), 259-276.
[17] Suzuki, Y., and Kaneko, K. (2003). An algorithm for node-disjoint paths in pancake graphs. IEICE TRANSACTIONS on Information and Systems, 86(3), 610-615.
[18] Yang, J. S., Wu, M. R., Chang, J. M., and Chang, Y. H. (2015). A fully parallelized scheme of constructing independent spanning trees on Möbius cubes. The Journal of Supercomputing, 71(3), 952-965.
[19] Zehavi, A., and Itai, A. (1989). Three tree-paths. Journal of Graph Theory, 13(2), 175-188.