臺灣博碩士論文加值系統

一個圖形的兩個擴展樹(spanning trees)如果有共同的樹根(root)，而且由此樹根到任一點的路徑為點相離(internally disjoint)，則稱二樹為互相獨立。多個擴展樹如果兩兩獨立，則稱之為一組“獨立擴展樹”(independent spanning trees)。
在分散式電腦系統中，獨立擴展樹的建構可以使訊息廣播(broadcasting)具有容錯性。因為網路中任意一節點按其在不同獨立擴展樹中的位置，接收來自其父節點的訊息，並傳遞給其子節點，即可容許若干節點失效仍能完成訊息廣播程序。Zehavi和Itai二位學者在1989年猜測任何k-連結的圖形，以任意點做根，都有k個獨立擴展樹。此一猜測對k>4的一般圖而言，仍為未解問題。
本篇論文主要目的，在某些特殊連結網路圖形上，探討其獨立擴展樹的建構問題，第一類為“弦環圖形”(chordal rings), Iwasaki等人[Information Processing Letters 69 (1999) 155–160]已提出線性時間找出四棵獨立擴展樹的演算法，我們將要提出新的線性時間演算法，可改善每棵獨立擴展樹的高度。
第二類為“超方體”Qk (hypercubes), Tang等人 [Journal of Information Science and Engineering 20 (2004) 605–617]利用遞迴方式，在k維的Qk，利用Qk-1已完成的獨立擴展樹結果，再建構Qk的獨立擴展樹，這種方法不能發展平行的演算法。在本篇論文，提出新的簡單又可平行的演算法，同時在獨立擴展樹的高度、平均路徑和時間複雜度也都是最佳解。
最後我們探討的圖形稱為“遞迴環形圖”(recursive circulant graph)，依照定義，如果G(cdm,d)是一個遞迴環形圖(其中0 < c < d, 而且m > 0)，則該圖有N=cd^m個點，編號從0到N-1。因為圖形G(cd^m,d)包含d個G(cd^{m-1},d)的子圖，故稱為“遞迴”環形圖。遞迴環形圖G(cdm,d)的degreeδ為2m-1, 2m, 2m+1或2m+2，如果Zehavi和Itai的猜想為真，以任意一點為根，應可在其上建構δ棵獨立擴展樹。本論文即欲找出正確有效的建構演算法以證明此一猜想在遞迴環形圖為真。

The vertex set and the edge set of a graph G are denoted by V (G) and E(G), respectively.Two paths P and Q connecting a vertex x to a vertex y are said to be internally disjoint, denoted by P||Q. A tree T is called a spanning tree of a graph G if V (T) = V (G). Further, T is a rooted spanning tree if it provides a specified vertex called the root of T. Let x and y be two vertices in T. We denote T[x, y] as the unique path from x to y in T. Two spanning trees T and T0 of a graph G are said to be independent if they are rooted at the same vertex, say r, and such that T[r, x] || T0[r, x] for every vertex x 2 V (G) \ {r}. Also, we refer a set of spanning trees of G to be independent if they are pairwise independent.

Finding multiple independent spanning trees has applications on the reliable communication protocols. The fault tolerance can be achieved by sending k copies of the message along the k independent spanning trees rooted at the source node. Recently, the problem of constructing multiple independent spanning trees of a given graph has received much attention. However, this problem is very hard on arbitrary graphs. In fact, Zehavi and Itai [Journal of Graph Theory 13 (1989) 175–188] conjectured that for any k-connected graph G and each vertex r of G, there exist k independent spanning trees of G rooted at
r. This conjecture still remains open for arbitrary k-connected graphs when k 5. In this dissertation, we shall propose efficient algorithms for finding independent spanning trees on chordal rings, hypercubes and recursive circulant graphs. The first interconnection network which we are concerned with is a particular family of regular 4-connected graphs, called chordal rings. Chordal rings are a variation of ring networks. By adding two extra links (or chords) at each vertex in a ring network, the reliability and fault-tolerance of the network are enhanced. Iwasaki et al. [Information
Processing Letters 69 (1999) 155–160] proposed a linear time algorithm for finding four independent spanning trees on a chordal ring. We shall give a new linear time algorithm for generating four independent spanning trees with a reduced height in each tree. Moreover, a complete analysis of our improvement on the heights of independent spanning trees is also provided.

The second interconnection network which we are concerned with is hypercubes. Tang et al. [Journal of Information Science and Engineering 20 (2004) 143–155] studied the problem of constructing k independent spanning trees on k-dimensional hypercube Qk, and provided a recursive construction algorithm (i.e., for constructing k independent spanning trees of Qk, it needs to build k − 1 independent spanning trees of Q_{k−1} in advance). Their algorithm forbids the possibility of parallelized. In this dissertation, based on a
simple concept called Hamming distance Latin square, we shall design a new algorithm for generating k independent spanning trees of Qk. The newly proposed algorithm relies on a simple rule and is easy to be parallelized. As a result, we show that the independent spanning trees we constructed are optimal in the sense that both the heights and the average path length of trees are minimized.

The third interconnection network which we are concerned with is recursive circulant graphs. A recursive circulant graph R(N, d) has N = cd^m vertices, where 0 < c < d. R(cd^m, d) is regular with degree, where degree is 2m−1, 2m, 2m+1 or 2m+2, depending on the value of parameters c and d. In this dissertation, we shall propose a parallel algorithm to construct independent spanning trees rooted at any vertex in a recursive circulant graph.

1 Introduction 1
1.1 1.1 Motivation and Intentions
1.2 outline
2 Interconnection Networks
2.1 Chordal Rings
2.2 HyperCubes
2.3 Recursive Circulant Graphs
3 Independent Spanning Trees On Chordal Rings
3.1 Preliminaries .
3.2 Refined Procedures for Case [N]_d<>0
3.3 Refined Procedures for Case [N]_d = 0
3.4 Analysis of Ours Improvement
3.5 Concluding remarks
4 Independent Spanning Trees On HyperCubes
4.1 Preliminaries
4.2 Constructing Independent Spanning Trees on Qk
4.3 Concluding remarks
5 Independent Spanning Trees On Recursive Circulant Graphs
5.1 Preliminaries
5.2 Constructing Independent Spanning Trees on R(2^m, 2)
5.3 Constructing Independent Spanning Trees on R(cdm, d),d>2
5.4 Concluding Remarks
6 Conclusion and Future Works

[1] T. Araki and Y. Shibata, Pancyclicity of recursive circulant graphs, Information Processing Letters, 81 (2002) 187–190. Erratum, 84 (2002) 173.
[2] T. Araki, Edge-pancyclicity of recursive circulants, Information Processing Letters, 88 (2003) 287–292.
[3] B.W. Arden, H. Lee, Analysis of chordal ring network, IEEE Transactions on Computers,C-30 (1981) 291–295.
[4] F. Bao, Y. Igarashi, and S.R. ¨Ohring, Reliable broadcasting in product networks,Discrete Applied Mathematics, 83 (1998) 3–20.
[5] J.C. Bermond, F. Comellas, D.F. Hsu, Distributed loop computer networks: A survey,Journal of Parallel and Distributed Computing, 24 (1995) 2–10.
[6] D.K. Biss, Hamiltonian decomposition of recursive circulant graphs, Discrete Mathematics, 214 (2000) 89–99.
[7] N. Chalamaiah, B. Ramamurthy, Finding shortest paths in distributed loop networks, Information Processing Letters, 67 (1998) 157–161.
[8] J. Cheriyan, S.N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms, 9 (1988) 507–537.
[9] I. Chung, Application of the special latin squares to the parallel routing algorithm on hypercube, Journal of Korean Information Science Society, 19(5) (1992).
[10] I. Chung, Construction of a parallel and shortest routing algorithm on recursive circulant networks, in: Proc. 4th International Conference on High Performance Computing in the Asia-Pacific Region, Beijing, China, 2000, 580–585.
[11] S. Curran, O. Lee, X. Yu, Finding four independent trees, SIAM Journal on Computing, 35 (2006) 1023-1058.
[12] D.Z. Du, D.F. Hsu, Q. Li, J. Xu, A combinational problem related to distributed loop networks, Networks, 20 (1990) 173–180.
[13] P. Erdos, F.D. Hsu, Distributed loop network with minimum transmission delay, Theoretical Computer Science, 100 (1992) 223–241.
[14] Z. Ge and S.L. Hakimi, Disjoint rooted spanning trees with small depths in deBruijn and Kautz graphs, SIAM Journal on Computing, 26 (1997) 79–92.
[15] F. Harary, J.P. Hayes, and H.J. Wu, A survey of the theory of hypercube graphs, Computational Mathematics and Applications, 15 (1988) 277–289.
[16] T. Hasunuma and H. Nagamochi, Independent spanning trees with small depths in iterated line digraphs, Discrete Applied Mathematics, 110 (2001) 189–211.
[17] C.-T. Ho, Full bandwidth communications on folded hypercubes, in Proc.1990 Int. Conf. Parallel Processing, vol. I, Penn State, (1990) 276–280.
[18] A. Huck, Independent trees in graphs, Graphs and Combinatorics, 10 (1994) 29–45.
[19] A. Huck, Independent trees in planar graphs, Graphs and Combinatorics, 15 (1999) 29–77.
[20] A. Itai, M. Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation, 79 (1988) 43–59.
[21] A. Itai , A. Zehavi, Three tree-paths, J. Graph Theory, 13 (1989) 175–188.
[22] Y. Iwasaki, Y. Kajiwara, K. Obokata, Y. Igarashi, Independent spanning trees of chordal rings, Information Processing Letters, 69 (1999) 155–160.
[23] S.L. Johnsson and C.-T. Ho, Optimum broadcasting and personalized communication in hypercube, IEEE Transactions on Computing, 38(9) (1989) 1249–1268.
[24] C. Kim, J. Choi and H.S. Lim, Embedding full ternary trees into recursive circulants, in: Proc. First EurAsian Conference on Information and Communication Technology, Shiraz, Iran, 2002, 874–882.
[25] S. Kim and I. Chung, Application of the special Latin square to a parallel routing algorithm on a recursive circulant network, Information Processing Letters, 66 (1998) 141–147.
[26] S. Kim and I. Chung, Application of the special Latin square to a parallel routing algorithm on a recursive circulant network, Information Processing Letters, 66 (1998) 141–147.
[27] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.
[28] H.S. Lim, J.H. Park and K.Y. Chwa, Embedding trees in recursive circulants, Discrete Applied Mathematics, 69 (1996) 83–99.
[29] C. Micheneau, Disjoint Hamiltonian cycles in recursive circulant graphs, Information Processing Letters, 61 (1997) 259–264.
[30] K. Mukhopadhyaya, B.P. Sinha, Fault-tolerant routing in distributed loop networks, IEEE Transactions on Computers, 44 (1995) 1452–1456.
[31] K. Miura, D. Takahashi, S. Nakano, and T. Nishizeki, A linear-time algorithm to find four independent spanning trees in four-connected planar graphs, Proc. 24th Workshop on Graph-Theoretic Concepts in Computer Science, WG’98, LNCS 1517, Springer (1998), pp. 310-323.
[32] K Miura, D Takahashi, SI Nakano, and T Nishizeki, A linear-time algorithm to find four independent spanning trees in four connected planar graphs, International Journal of Foundations of Computer Science, 10 (1999) 195–210.
[33] L. Narayanan, J. Opatrny, Compact routing on chordal rings of degree 4, Algorithmica, 23 (1999) 72–96.
[34] S. Nagai and S. Nakano, A linear-time algorithm to find independent spanning trees in maximal planar graphs, Proc. 26th Workshop on Graph-Theoretic Concepts in Computer Science, WG 2000, LNCS 1928, Springer (2000) 290–301.
[35] K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi, Independent spanning trees of product graphs and their construction, IEICE Trans. Fundamentals of Electronics, Communications and Computer Sciences, E79-A (1996) 1894–1903.
[36] B. Parhami, D.M. Kwai, Periodically regular chordal rings, IEEE Transactions on Parallel and Distributed Systems, 10 (1999) 658–672.
[37] J.H. Park, Strong hamiltonicity of recursive circulants, Journal of Korean Information Science Society, 28 (2001) 742–744.
[38] J.H. Park and K.Y. Chwa, Recursive circulant: A new topology for multicomputer networks, in: Proc. of International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN’94), Kanazawa, Japan, 1994, 73–80.
[39] J.H. Park and K.Y. Chwa, Recursive circulants and their embeddings among hypercubes, Theoretical Computer Science, 244 (2000) 35–62.
[40] M.O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM, 36 (1989) 335–348.
[41] P. Ramanathan and K. G. Shin, Reliable broadcast in hypercube multicomputers, IEEE Transactions on Computers, 37(12) (1988) 1654–1657.
[42] I. Stojmenovic, Multiplicative circulant networks: Topological properties and communication algorithms, Discrete Applied Mathematics, 77 (1997) 281–305.
[43] S.M. Tang, Y.L. Wang, and Y.H. Leu, Optimal independent spanning trees on hypercubes, Journal of Information Science and Engineering, 20 (2004), pp. 143–155.
[44] C.H. Tsai, Jimmy J.M. Tan, Y.C. Chuang and L.H. Hsu, Hamiltonian properties of faulty recursive circulant graphs, Journal of Interconnection Networks, 3 (2002) 273–289.
[45] C.H. Tsai, Jimmy J.M. Tan and L.H. Hsu, The super-connected property of recursive circulant graphs, Information Processing Letters, 91 (2004) 293–298.
[46] C.K. Wong, D. Coppersmith, A combinatorial problem related to multimode memory organizations, Journal of the ACM 21 (1974) 392–402.
[47] J.S. Yang, J.M. Chang, S.M. Tang, and Y.L. Wang, Reducing the height of independent spanning trees in chordal rings, IEEE Transactions on Parallel and Distributed Systems, to appear.
[48] J.S. Yang, S.M. Tang, J.M. Chang and Y.L. Wang, Parallel construction of optimal independent spanning trees on hypercubes, Parallel Computing, to appear.
[49] X. Yang, D.J. Evans and G.M. Megson, Maximum induced subgraph of a recursive circulant, Information Processing Letters, 95 (2005) 293–298.
[50] A. Zehavi, A. Itai, Three tree-paths, Journal of Graph Theory, 13 (1989) 175–188.
[51] G.W. Zimmerman, A.H. Esfahanian, Chordal rings as fault-tolerant loops, Discrete Applied Mathematics, 37/38 (1992) 563–573.