臺灣博碩士論文加值系統

在互聯網路中，資料傳輸分配與容錯網路設計在當中扮演重要的服務。這篇研究提出了有效的演算法來改善網路之間的連結。作為一種凱萊圖，置換圖網路以被廣泛使用在當今的網路結構中。當網路節點損壞後，即時的重新連接是使用者想要的，快速搜尋另一條節點不相交的路徑即所需解決的問題。本篇基於置換圖網路研究中，我們擴大範圍建構獨立生成樹以達最大化容錯。

In interconnection networks, data distribution and fault tolerance are crucial services. This study proposes an effective algorithm for improving connections between networks. Transposition networks are a type of Cayley graphs and have been widely used in current networks. Whenever any connection node fails, users want to reconnect as rapidly as possible, it is urgently in need to construct a new path. Thus, searching node-disjoint paths is crucial for finding a new path in networks. In this thesis, we expand the target to construct independent spanning trees to maximize the fault tolerance of transposition networks.

1 Introduction 1
2 Preliminaries 3
3 Constructing Independent Spanning Trees on Tn 7
3.1 Common functions for construction ...................... 7
3.2 Constructing independent spanning trees on T3 . .............. 10
3.3 Constructing independent spanning trees on Tn . .............. 13
4 Proof of algorithm validity 31
5 Conclusion 37

[1] Akers, S. B., ＆ Krishnamurthy, B. (1989). A group-theoretic model for symmetric interconnection networks.
IEEE Transactions on Computers, 38(4), 555-566.

[2] Bao, F., Funyu, Y., Hamada, Y., ＆ 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] Chase, P. J. (1973). Transposition graphs.
SIAM Journal on Computing, 2(2), 128-133.

[4] Clark, D. (2005). Transposition graphs: An intuitive approach to the parity theorem for permutations.
Mathematics Magazine, 78(2), 124-130.

[5]Feng, Y. Q. (2006). Automorphism groups of cayley graphs on symmetric groups with generating transposition sets.
Journal of Combinatorial Theory, Series B, 96(1), 67-72.

[6] Ganesan, A. (2015). Automorphism group of the complete transposition graph.
Journal of Algebraic Combinatorics, 42(3), 793-801.

[7] Itai, A., ＆ Rodeh, M. (1988). The multi-tree approach to reliability in distributed networks.
Information and Computation, 79(1), 43-59.

[8] Jwo, J. S. (1996). Properties of Star Graph, Bubble-sort Graph, Perfix-reversal Graph and Complete-transposition Graph.
Journal of Information Science and Engineering, 12(4), 603-617.

[9] Khuller, S., ＆ Schieber, B. (1992). On independent spanning trees
Information Processing Letters, 42(6), 321-323.

[10] Lakshmivarahan, S., Jwo, J. S., ＆ Dhall, S. K. (1993). Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey.
Parallel Computing, 19(4), 361-407.

[11] Latifi, S., ＆ Srimani, P. K. (1996). Transposition networks as a class of fault-tolerant robust networks.
IEEE Transactions on Computers, 45(2), 230-238.

[12] Suzuki, Y., Kaneko, K., ＆ Nakamori, M. (2006). Node-disjoint paths algorithm in a transposition graph.
IEICE Transactions on Information and Systems, 89(10), 2600-2605.

[13] Walker, R. (1992). Implementing discrete mathematics: combinatorics and graph theory with Mathematica, Steven Skiena. Pp 334. 1990. ISBN 0-201-50943-1 (Addison-Wesley).
The Mathematical Gazette, 76(476), 286-288.

[14] Xu, M. Y. (1998). Automorphism groups and isomorphisms of Cayley digraphs.
Discrete Mathematics, 182(1-3), 309-319.