臺灣博碩士論文加值系統

我們通常將網路拓樸結構以圖形來表示，點代表處理器，邊代表處理器間的連線
關係。在圖形上，我們說一組擴展樹是獨立的，代表如果所有的樹的樹根為同一
個節點r 和樹上的任一點v，r 到v 的路徑上，除了r 和v 以外所經過的點都不
相同。獨立擴展樹對於在網路資料廣播提供很多優點，其中包括增加了容錯和頻
寬。階層式交叉立方體(HCCk;n) 是由k 維度的超立方體以及n 維度交叉立方體
建構而成，在本文中我們研究一些算法來建構階層式交叉立方體HCCk;n 的n 棵
獨立擴展樹。

A topology of a interconnection network is usually denoted by a graph where nodes
represent processors and edges represent links between processors. If all the trees are
rooted at the same node r and for any other node v(̸= r), the paths from v to r in
any two trees are node disjoint except the two end nodes v and r, a set of spanning
trees in a graph is said to be independent (ISTs for short). The independent spanning
trees for data broadcasting in networks provide a number of advantages that
included the increase of fault-tolerance and bandwidth. Hierarchical crossed cubes
is constructed by k-dimensional hypercubes and a n-dimensional crossed cubes and
denoted by HCCk;n. In this paper, we study some algorithms to construct n ISTs
in a HCCk;n.

誌謝. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i
中文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
英文摘要. . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv
圖目錄. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 Hypercubes . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Crossed cubes . . . . . . . . . . . . . . . . . . . . . . . 6
2.3 Hierarchical crossed cubes . . . . . . . . . . . . . . . . . 7
2.4 Acronyms and the architecture of algorithms . . . . . . . . 8
3 Constructing n ISTs in a HCC1;n . . . . . . . . . . . . . . . 11
3.1 The construction of virtual independent spanning trees in a HCC1;n . .11
3.2 The construction of ISTs in a CQn . . . . . . . . . . . . . 16
3.3 Constructing strictly ISTs in a CQn . . . . . . . . . . . . 18
3.4 Constructing real ISTs in a HCC1;n . . . . . . . . . . . . .22
4 Constructing real ISTs in a HCCk;n . . . . . . . . . . . . . 25
4.1 Constructing virtual Hamiltonian path in a HCCk;n . . . . . 26
4.2 Constructing n ISTs in a HCCk;n . . . . . . . . . . . . . . 27
5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 33
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . 35

[1] J. A. Bondy and U. S. R. Murty: Graph Theory with Applications. North
Holland, New York, (1980)
[2] F. Bao, Y. Funyu, Y. Hamada, and Y. Igarashi: Reliable broadcasting and
secure distributing in channel networks. In : Proc. of 3rd International Symposium
on Parallel Architectures, Algorithms and Networks, 472-478 (1997).
[3] J. C. Bermond, A. Ferreira, S. Perennes, and J. G. Peters: neighbourhood
broadcasting in hypercubes. In : SIAM J. Discrete Math. vol. 4, pp. 823-843
(2007)
[4] M. S. Chen and K. G. Shin: Processor Allocation in an n-Cube Multiprocessor
Using Gray Codes. In: IEEE Trans. on Computers, vol. 36, no. 12, pp. 1,396-
1,407 (1987)
[5] J. Cheriyan and S. N. Maheshwari: Finding nonseparating induced cycles and
independent spanning trees in 3-connected graphs. In : J. Algorithms, 9, 507-
537 (1988).
[6] X. B. Chen: Parallel construction of optimal independent spanning trees on
Cartesian product of complete graphs. In : Inform. Process. Lett., 111, 235-238
(2011).
[7] S. Curran, O. Lee, and X. Yu: Finding four independent trees. In : SIAM J.
Comput., 35, 1023-1058 (2006).
[8] B. Cheng, J. Fan, X. Jia, and J. Jia : Parallel construction of independent
spanning trees and an application in diagnosis on Möbius cubes. In : J. Supercomput.,
65, 1279-1301 (2013) .
[9] B. W. Douglas: Introduction to Graph Theory. In : 2nd ed, Prentice Hall
(2001).
[10] T. Dvorak and P. Gregor : Partitions of faulty hypercubes into paths with
prescribed end vertices. In : SIAM J. Discrete Math. vol. 4, pp. 1,448-1,461
(2008)
[11] K. Efe: The Crossed Cube Architecture for Parallel Computing. In : IEEE
Trans. Parallel and Distributed Systems, vol. 3, no. 5, pp. 513-524 (1992)
[12] Z. Ge and S.L. Hakimi: Disjoint rooted spanning trees with small depths in
deBruijn and Kautz graphs In : SIAM Journal on Computing, 26 (1997), pp.
79–92
[13] T. Hasunuma and H. Nagamochi : Independent spanning trees with small
depths in iterated line digraphs In : Discrete Applied Mathematics, 110 (2001),
pp. 189–211
[14] A. Huck: Independent trees in graphs. In : Graphs Combin., 10, 29-45 (1994).
[15] A. Huck: Independent trees in planar graphs. In : Graphs Combin., 15, 29-77
(1999).
[16] A. Itai and M. Rodeh: The multi-tree approach to reliability in distributed
networks. In : Inform. Comput., 79, 43-59 (1988).
[17] Y. Iwasaki, Y. Kajiwara, K. Obokata, and Y. Igarashi: Independent spanning
trees of chordal rings. In : Inform. Process. Lett., 69, 155-160 (1999).
[18] J. S. Kim, H. O. Lee, E. Cheng, and L. Lipták: Independent spanning trees on
even networks. In : Inform. Sci., 181, 2892-2905 (2011).
[19] J. S. Kim, H. O. Lee, E. Cheng, and L. Lipták: Optimal independent spanning
trees on odd graphs. In : J. Supercomputing, 56, 212-225 (2011).
[20] P. L. Lai, H. C. Hsu, C. H. Tsai, and I. A. Stewart: A class of hierarchical graphs
as topologies for interconnection networks star. In : Theoretical Computer
Science, vol. 411, no. 31-33, pp. 2,912-2,924 (2010).
[21] F. T. Leighton: Introduction to Parallel Algorithms and Architectures : arrays,
trees, hypercubes. San Mateo: Morgan Kaufman (1992).
[22] W. Y. Lin and P. L. Lai: A study of construction of independent spanning trees
in hierarchical crossed cubes. 2014.
[23] Y. J. Liu, J. K. Lan, W. Y.Chou, and C. Chen: Constructing independent
spanning trees for locally twisted cubes. In : Theoret. Comput. Sci., 412, 2237-
2252 (2011).
[24] K. Miura, D. Takahashi, S. Nakano, T. Nishizeki,: A linear-time algorithm
to find four independent spanning trees in four-connected planar graphs. In :
International Journal of Foundations of Computer Science, 10 (1999), pp. 195–
210.
[25] S. Nagai and S. Nakano: A linear-time algorithm to find independent spanning
trees in maximal planar graphs Proceedings of 26th Workshop on Graph-
Theoretic Concepts in Computer Science, WG 2000, LNCS 1928, Springer
(2000), pp. 290–301
[26] K. Obokata, Y. Iwasaki, F. Bao, and Y. Igarashi: Independent spanning trees
of product graphs and their construction. In : IEICE Trans. Fund. Electron.
Comm. Comput. Sci., E79-A 1894-1903 (1996) .
[27] A. A. Rescigno: Vertex-disjoint spanning trees of the star network with applications
to faulttolerance and security. In : Inform. Sci., 137, 259-276 (2001).
[28] S. M. Tang, Y. L. Wang, and Y. H. Leu: Optimal independent spanning trees
on hypercubes In : Journal of Information Science and Engineering, 20 (2004),
pp. 143–155
[29] Y. Wang, J. Fan, G. Zhou, and X. Jia: Independent spanning trees on twisted
cubes. In : J. Parallel Distrib. Comput., 72, 58-69 (2012) .
[30] J. D. Wang, J. M. Chang, J. S. Yang, and K. F. Ding: Independent Spanning
Trees on Crossed Cubes. In : Proceedings of the 31st Workshop on Combinatorial
Mathematics and Computation Theory., 66-72 (2014).
[31] J. Xu: Topological Structure and Analysis of Interconnection Networks.
Kluwer, Dordrecht (2001).
[32] J. S. Yang, J. M. Chang, S. M. Tang, and Y. L. Wang: Reducing the height of
independent spanning trees in chordal rings. In : IEEE Trans. Parallel Distrib.
Syst., 18, 644-657 (2007).
[33] J. S. Yang, H. C. Chan, and J. M. Chang: Broadcasting secure messages via
optimal independent spanning trees in folded hypercubes. In : Discrete Appl.
Math., 159, 1254-1263 (2011).
[34] J. S. Yang, M. R. Wu, J. M Chang and Y. H. Chang: (2015) A fully parallelized
scheme of constructing independent spanning trees on Möbius cubes. In : The
Journal of Supercomputing 71, 952-965. Online publication date: 1-Mar-2015.
[35] A. Zehavi, and A. Itai: Three tree-paths. In : J. Graph Theory, 13, 175-188
(1989).
38