臺灣博碩士論文加值系統

(n,k)-星圖是星型網路的擴展化版本並且是超立方體的一個非常有吸引力的替代圖形。在k = n - 1的情況下(n,k)-星圖相似於星型路。它具有非常多的優異特性，例如：點對稱、分層構造、最大化容錯和簡單的最短路徑路由方法等。圖G上的一組生成樹如果所有的樹的根節點都是點r，並且對於圖中其他的所有不同於r的點v，在任意兩棵樹中從v到r的兩條路徑，除v和r以外的不會有其他相同節點，這樣我們就叫這一組生成樹為一組獨立生成樹。獨立生成樹在網路廣播和安全信息分發等應用領域有很多利用價值。在本篇碩士論文中，我們將給出一個遞回式對的演算法，其可以在(n, k)-星圖上構造出n -1棵獨立生成樹。

The (n,k)-star graphs is a generalized version of the star network and an attractive alternative to the hypercube. It is isomorphic to the n-star graph if k = n - 1. It preserves many attractive properties of an star network such as vertex symmetry, hierarchical structure, maximal fault tolerance, and simple shortest routing. A set of spanning trees in a graph G is called independent spanning trees (ISTs for short) if they are rooted at the same vertex, say r, and for each vertex v(v!= r) in G, the two paths from v to r in any two trees share no common vertex expect for v and r. ISTs have a number of advantages for broadcasting and secure message distribution in interconnection network eld. In this thesis, we present a recursively approach to construct n -1 ISTs on (n,k)-star graphs.

Abstract in Chinese i
Abstract in English ii
Acknowledge iii
Contents iv
List of Figures vi
1 Introduction 1
2 Related work 3
2.1 Theoretical resultes about ISTs . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2 Applications about ISTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Preliminaries 6
4 The Algorithm for Constructing ISTs of Sn;k 8
4.1 Constructing vertex disjoint paths . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 Constructing ISTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5 Correctness 29
6 Conclusions 38
Bibliography 39

[1] F. Bao, Y. Funyu, Reliable Broadcasting and Secure Distributing in Channel Networks, Proceedings of 3rd International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN 1997) , 56(5) (1997) 472-478.
[2] J.H. Chang, J. Kim, Ring Embedding in Faulty (n; k)-Star Graphs, Proceedings Eighth International Conference on Parallel and Distributed Systems. ICPADS 2001, (2001) 99-106.
[3] Y.S. Chen, 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, (2000) 217-224.
[4] J. Cheriyan, S.N. Maheshwari, Finding Nonseparating Induced Cycles and Independent Spanning Trees in 3-Connected Graphs, Journal of Algorithms, 9(4) (1988) 507-537.
[5] W.K. Chiang, R.J. Chen, The (n; k)-Star Graph: A Generalized Star Graph, Information Processing Letters, 56(5) (1995) 259-264.
[6] W.K. Chiang, R.J. Chen, Topological Properties of the (n; k)-Star Graph, International Journal of Foundations of Computer Science, 9(2) (1998) 235-248.
[7] S. Curran, O. Lee, X. Yu, Finding Four Independent Trees, SIAM Journal of Computer, 35(5) (2006) 1023-1058.
[8] Z.Y. Ge, S.L. Hakimi, Disjoint Rooted Spanning Trees with Small Depths in deBruijn and Kautz Graphs, SIAM Journal of Computers, 26(1) (1997) 79-91.
[9] 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, 42 (2003) 189-201.
[10] H.C. Hsu, C.K. Lin, H.M. Hung, L.H. Hsu, The Spanning Connectivity of the (n; k)-Star Graphs, International Journal of Foundations of Computer Science, 17 (2006) 415-434.
[11] H.C. Hsu, C.J. Tu, Constructing Edge-Disjoint Spanning Trees in Locally Twisted Cubes, Theoretical Computer Science, 410 (2009) 926-932.
[12] H.C. Hsu, C.-Y. Wu, Edge-Fault-Tolerant Hamiltonicity of Locally Twisted Cubes under Conditional Edge Faults, Journal of Combinatorial Optimization, 19(1) (2010) 2010-2019.
[13] A. Huck, Independent Trees in Graphs, Graphs and Combinatorics, 10(1) (1994) 29-45.
[14] A. Huck, Independent Trees in Planar Graphs, Graphs and Combinatorics, 15(1) (1999) 29-77.
[15] Y. Iwasaki, Y. Kajiwara, K. Obokata, Y. Igarashi, Independent Spanning Trees of Chordal Rings, Information Processing Letters, (1999) 155-160.
[16] A. Itai, M. Rodeh, The Multi-Tree Approach to Reliability in Distributed Networks, Information and Computation, 79 (1988) 43-59.
[17] S.S. Kao, J.M. Chang, K.J. Pai, R.Y.Wu, A Parallel Construction of Vertex-Disjoint Spanning Trees with Optimal Heights in Star Networks, International Conferenceon Combinatorial Optimization and Applications 2017, 10627 (2017) 41-55.
[18] J.S. Kim, H.O. Lee, E. Cheng, L. Lipt ak, Independent Spanning Trees on Even Networks, Information Sciences, 181(13) (2011) 2892-2905.
[19] J.S. Kim, H.O. Lee, E. Cheng, L. Lipt ak, Optimal Independent Spanning Trees on Odd Graphs, Journal of Supercomputing, 56(2) (2011) 212-225.
[20] T.C. Lin, D.R. Duh, The Spanning Connectivity of the (n; k)-Star Graphs, International Journal of Foundations of Computer Science, 17 (2006) 415-434.
[21] S. Nagai, S. Nakano, A Linear-Time Algorithm to Find Independent Spanning Trees in Maximal Planar Graphs, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E84-A (2001) 1102-1109.
[22] K. Obokata, Y. Iwasaki, F. Y. Igarash, Independent Spanning Trees of Product Graphs and Their Construction. IEICE Transactions Fundamentals of Electronics, Communications and Computer Science, 79 (1996) 1894-1903.
[23] A.A. Rescigno, Vertex-Disjoint Spanning Trees of the Star Network with Applications to Fault-Tolerance and Security, Information Sciences, 137 (2001) 259-276.
[24] J.S. Yang, J.M. Chang, S.M. Tang, Y.L. Wang, Parallel Construction of Optimal Independent Spanning Trees on Hypercubes, Parallel Computing, 33 (2007) 73-79.
[25] J.S. Yang, J.M. Chang, Independent Spanning Trees on Folded Hyper-Stars, Networks, 56(4) (2010) 44-53.
[26] J.S. Yang, H.C. Chan, J.M. Chang, A Near-Optimal Broadcasting in (n; k)-Star Graphs, in: Proc. ACIS Int. Conf. on Software Engineering Applied to Networking and Parallel Distributed Computing, (2000) 217-224.
[27] A. Zehavi, A. Itai, Three Tree-Paths, Journal of Graph Theory, 13(2) (1989) 175-188.