臺灣博碩士論文加值系統

藉由建構同根的多棵獨立展開樹，可以確保容錯廣播和安全傳訊。
廣義蜂巢環面網路上的每個點有三個鄰居，是3-規則，而且各點之間可以互轉，具有自同構特性。
本文提出的演算法可以在蜂巢環面網路上，以任一點為根，可以建構三棵獨立展開樹。不同於以前所提方法之處在於，此一演算法可以平行化。

Two spanning trees of a given network are said to be independent if they are rooted at the same node, say r, and for each node v≠r two different paths from r to v, one path in each tree, are internally disjoint. A set of spanning trees of the network is said to be independent if they are pairwise independent.
The independent spanning trees (IST for short) problem has applications in fault-tolerance broadcasting and secure message distribution. It is equivalent to the
one-to-many routing problem of a given network. That is, constructing multiple IST
rooted at one node can achieve the one-to-many routing of the network.
A generalized honeycomb torus (GHT for short) is formed by adding wraparound
edges on a honeycomb mesh. A GHT is 3-regular and node-transitive. Since a GHT
is node-transitive, without loss of generality, we only consider one node as the root
of the IST.
In this thesis, we proposed an algorithm to construct three IST based on the
decision of individual node in a given GHT. Unlike the traditional algorithm, our
algorithm parallelizes the construction of the IST.

摘要  I
Abstract II
誌謝 III
Contents IV
List of Tables VI
List of Figures VII
1 Introduction 1
1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation and Intentions . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Preliminary 3
2.1 Generalized Honeycomb Tori . . . . . . . . . . . . . . . . . . . . . . 3
2.2 The Transitivity of a Generalized Honeycomb Torus . . . . . . . . . 4
2.3 Related Studies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3 Main Result 6
3.1 Basic Ideas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.2 Parallel Construction of Independent Spanning Trees . . . . . . . . . 8
3.2.1 Algorithm Parent Direct 1 . . . . . . . . . . . . . . . . . 9
3.2.2 Algorithm Parent Direct 2 . . . . . . . . . . . . . . . . . 11
3.2.3 Algorithm Parent Direct 3 . . . . . . . . . . . . . . . . . 11
3.2.4 Algorithm Parent Direct 4 . . . . . . . . . . . . . . . . . 13
3.2.5 Algorithm Parent Direct 5 . . . . . . . . . . . . . . . . . 15
3.2.6 Algorithm Parent Direct 6 . . . . . . . . . . . . . . . . . 18
4 Correctness Proof 20
4.1 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
4.2 Independency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
5 Conclusion and Future Works 26
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
5.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Bibliography 27

[1] B. Alspach and M. Dean, Honeycomb toroidal graphs are Cayley graphs, Information Processing Letters 109 (2009) 705-708.
[2] J. Carle, J. Myoupo, and D. Seme, All-to-all broadcasting algorithms on honeycomb networks and applications, Parallel Processing Letters 9 (1999) 539-550.
[3] H.-J. Cho and L.-Y. Hsu, Ring embedding in faulty honeycomb rectangular torus, International Journal of Computer Mathematics 84 (2002) 277-284.
[4] H.-J. Cho and L.-Y. Hsu, Generalized honeycomb tours, Information Processing Letters 86 (2003) 185-190.
[5] J. Cheriyan and S. N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms 9 (1988) 507-537.
[6] S. Curran, O. Lee and X. Yu, Finding four independent trees, SIAM Journal on Computing 35 (2006) 1023-1058.
[7] Q. Dong, X. Yang and J. Zhao, Embedding a fault-free Hamiltonian cycle in a class of faulty generalized honeycomb tori, Computers and Electrical Engineering 35 (2009) 942-950.
[8] Q. Dong, Q. Zhao and Y. An, The Hamiltonicity of generalized honeycomb torus networks, Information Processing Letters 115 (2015) 104-111.
[9] L.-Y. Hsu, F.-I Ling, S.-S. Kao and H.-J. Cho, Ring embedding in faulty generalized honeycomb torus GHT(m, n, n/2), International Journal of Computer Mathematics 87 (2010) 3344-3358.
[10] A. Itai and M. Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation 79 (1988) 43-59.
[11] Y. Iwasaki, Y. Kajiwara, K. Obokata and Y. Igarashi, Independent spanning trees of chordal rings, Information Processing Letters 69 (1999) 155-160.
[12] J.-C. Lin, J.-S. Yang, C.-C. Hsu and J.-M. Chang, Independent spanning trees vs. edge-disjoint spanning trees in locally twisted cubes, Information Processing Letters 110 (2010) 414-419.
[13] G. M. Megson, X. Yang and X. Liu, Honeycomb tori are Hamiltonian, Information Processing Letters 72 (1999) 99-103.
[14] G. M. Megson, X. Liu and X. Yang, Fault-tolerant ring embedding in a honeycomb torus with nodes failures, Parallel Processing Letters 9 (1999) 551-561.
[15] B. Parhami and D. M. Kwai, A unied formulation of honeycomb and diamond networks, IEEE Transactions on Parallel and Distributed Systems 12 (2001) 74-80.
[16] M. O. Rabin, Ecient dispersal of information for secursity, load balencing, and fault tolerance, Journal of the ACM 36 (1989) 335-348.
[17] A. A. Rescigno, Node-disjoint spanning trees of the star network with applications to fault-tolerance and security, Information Sciences 137 (2001) 259-276.
[18] Y.-K. Shih, Y.-C. Wu, S.-S. Kao and J. J.-M. Tan, Vertex-bipancyclicity of the generalized honeycomb tori, Computers and Mathematics with Applications 56 (2008) 2848-2860.
[19] I. Stojmenovic, Honeycomb networks: topological properties and communication algorithms, IEEE Transactions on Parallel and Distributed Systems 8 (1997) 1036-1042.
[20] S.-M. Tang, Y.-L. Wang and Y.-H. Leu, Optimal independent spanning trees on hypercubes, Journal of Information Science and Engineering 20 (2004) 605-617.
[21] S.-M. Tang, J.-S. Yang, Y.-L. Wang and J.-M. Chang, Independent spanning trees on multidimensional torus networks, IEEE Transactions on Computers 59 (2010) 93-102.
[22] S.-M. Tang, J.-S. Yang, J.-M. Chang and Y.-L. Wang, A one-to-many parallel routing algorithm on a generalized recursive circulant graph, Proc. of the 31st Workshop on Combinatorial Mathematics and Computation Theory (2014) 29-36.
[23] X. Yang, D. J. Evans, H. Lai and G. M. Megson, Generalized honeycomb torus is Hamiltonian, Information Processing Letters 92 (2004) 31-37.
[24] X. Yang, G. M. Megson, Y. Tang and D. J. Evans, Diameter of parallelogramic honeycomb torus, Computers and Mathematics with Applications 50 (2005) 1477-1486.
[25] J.-S. Yang and J.-M. Chang, Independent spanning trees on folded hyper-stars, Networks 56 (2010) 272-281.
[26] J.-S. Yang, J.-M. Chang and H.-C. Chan, Broadcasting secure messages via optimal independent spanning trees in folded hypercubes, Discrete Applied Mathematics 159 (2011) 1254-1263.
[27] J.-S. Yang, S.-M. Tang, J.-M. Chang and Y.-L. Wang, Parallel construction of independent spanning trees on hypercubes, Parallel Computing 33 (2007) 73-79.
[28] A. Zehavi and A. Itai, Three tree-paths, Journal of Graph Theory 13 (1989) 175-188.