臺灣博碩士論文加值系統

n維超立方體(hypercube)擁有許多良好的網路性質，常被廣泛地應用在互連網路中並被置入網路架構內，其為受人深入探討的互連網路架構之一。n維增廣立方體AQn (augmented cubes) 是超立方體的一種重要的變型架構 (hypercube variant)。增廣立方體不但保留住超立方體全部有利的特性，更具有比超立方體更良好的嵌入性質，例如容錯性更高，最短路徑更短。最近文獻中有許多學者探討一些AQn性質，例如邊互斥的漢彌爾頓迴路，其優點是當執行一個環狀結構的演算法時可以使訊息均勻的傳播至整個互連網路。如果一個互連網路G是路徑覆蓋 (path cover)，則是由一些節點互斥 (node-disjoint) 路徑的集合，且這些路徑包含G的所有節點。當G是一個等距路徑覆蓋 (isometric path cover) 時，即對於G中任兩對不同的節點us, ut和vs, vt，存在著2條路徑P和Q，並滿足：(1) 路徑P連結us和ut，路徑Q連結vs和vt，(2) |P| = |Q|，(3) 於G中每一節點只會出現一次在路徑P或Q中。找出一個互連網路上的等距路徑覆蓋可應用於該網路的路由問題 (routing problem) 上。
此論文中，我們首先證明當n大於等於3時，n維增廣立方體AQn包含2條邊互斥的漢彌爾頓迴路。接著證明當n大於等於2時，n維增廣立方體AQn是一個等距路徑覆蓋。從存在性的證明中，我們提出在線性時間內的演算法可以建構出2條邊互斥的漢彌爾頓迴路及一個等距路徑覆蓋。

The n-dimensional hypercube network Qn is one of the most popular interconnection networks since it has simple structure and is easy to implement. The n-dimensional augmented cube AQn, an important variation of the hypercube, possesses several embedding properties that hypercubes and other variations do not possess. The advantages of AQn are that the diameter is only about half of the diameter of Qn and it is node-symmetric. Recently, some interesting properties of AQn have been investigated in the literature. The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the interconnection network. A network G contains one isometric path cover and is called isometric path coverable if for any two distinct pairs of nodes us, ut and vs, vt of G, there exist two node-disjoint paths P and Q satisfying that (1) P joins us and ut , and Q joins vs and vt , (2) |P| = |Q|, and (3) every node of G appears in P and Q exactly once. In this thesis, we first prove that the augmented cube AQn contains two edge-disjoint Hamiltonian cycles for n is equal or greater than 3. We then prove that AQn, with n is equal or greater than 2, is isometric path coverable. Based on the proofs of existences, we further present linear time algorithms to construct two edge-disjoint Hamiltonian cycles and one isometric path cover in an n-dimensional augmented cube AQn.

Contents

Abstract in Chinese I
Abstract II
Acknowledgement III
Contents IV
List of Figure V
List of Table VII
1 Introduction 1
2 Terminology and Basic Notations 7
3 A Brief Survey on Augmented Cubes 12
3.1 Pancyclicity 12
3.2 Panconnectivity 17
3.3 Edge-fault Hamiltonicity of augmented cubes 19
4 Two Edge-Disjoint Hamiltonian Cycles 21
5 One Isometric path Cover 27
6 Concluding Remarks 35
References 36


List of Figures

Figure 1.1 The hypercubes Q1, Q2 and Q3…1
Figure 1.2 A dual-ring topology…4
Figure 2.1 (a) The 2-dimensional augmented cube AQ2, and (b) the 3 dimensional augmented cube AQ3 containing two sub-augmented cubes AQ20, AQ21, where the leading bits of nodes are underlined…9
Figure 2.2 The Hamiltonian connected property of AQk+1 for (a) Case 1, and (b) Case 2 of Lemma 2.2……11
Figure 3.1 Construct a cycle C of length l in AQn with 3 <= l <= 2n, where the solid line or dashed line indicate the edge and the dashed curved line indicate a path between two nodes……12
Figure 3.2 The AQn has two node-disjoint cycles, H and S, where the solid lines or dashed line indicate the edge and the dashed curved lines indicate a path between two nodes…… 14
Figure 3.3 Construct a cycle of length l belong {3, 4, ..., 2n} in AQn- F with |F| = n-1, where the solid lines or dashed line indicate the edge and the dashed curved lines indicate a path between two nodes……15
Figure 3.4 The AQn contains paths, between two distinct nodes u and v, of all lengths from their distance to 2n- 1, where the solid lines or dashed line indicate the edge and the dashed curved lines indicate a path between two nodes…… 18
Figure 3.5 A cycle C = (u, uh, P[uh, uc], uc, u) is still a Hamiltonian cycle in AQn when any (2n-3) edges are removed from AQn, where the solid lines indicate the edge and the dashed curved lines indicate a path between two nodes…… 19
Figure 3.6 A worst case scenario: four distinct nodes v1, v2, v3 and v4 in AQ2, v1 and v3 have 2n-3 faulty edges and (v1, v2), (v1, v4), (v2, v3) and (v3, v4) are fault-free, where the solid lines indicate the fault-free edges and the dashed lines indicate the faulty edges…20
Figure 4.1 Two edge-disjoint Hamiltonian paths (cycles) in AQ3, where the solid arrow lines indicate a Hamiltonian path P and the dashed arrow lines indicate the other edge-disjoint Hamiltonian path Q……22
Figure 4.2 The construction of two edge-disjoint Hamiltonian paths in AQk+1, with k => 3, where the dashed arrow lines indicate the paths and the solid arrow lines indicate concatenated edges.23
Figure 4.3 Two edge-disjoint Hamiltonian paths (cycles) in AQ4, where the solid arrow lines indicate a Hamiltonian path P and the dashed arrow lines indicate the other edge-disjoint Hamiltonian path Q……25
Figure 5.1 The constructions of two node-disjoint paths in AQk+1, with k => 2, for (a) us, ut, vs, vt are in AQk0, (b) us, ut, vs are in AQk0 and vt is in AQk1, (c) us, ut AQk0 and vs, vt belong AQk1, and (d) us, vs belong AQk0 and ut, vt belong AQk1, where the dashed arrow lines indicate the paths, the solid arrow lines indicate concatenated edges, and the symbol‘x’denotes the de-struction to an edge in a path……30

List of Tables
Table 3.1 The cycles of lengths 3 or 8 in AQ3. ............................................. 13
Table 3.2 Summary of the geodesic cycles with starting node u = 000 and
destination node v in AQ3. ............................................................ 16
Table 3.3 Some results of the balanced cycles with u = 000 and v in AQ3 ... 17

[1]E. Abuelrub, The Hamiltonicity of crossed cubes in the presence of faults, Engineering Letters 16(3) (2008) EL_16_3_26.
[2]M.M. Bae and B. Bose, `Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes, IEEE Trans. Comput. 52 (2003)1271-1284.
[3]B. Barden, R. Libeskind-Hadas, J. Davis and W. Williams, On edge-disjoint spanning trees in hypercubes, Inform. Process. Lett. 70 (1999) 13-16.
[4]L. N. Bhuyan and D. P. Agrawal, Generalized hypercube and hyperbus structures for a computer network, IEEE Trans. Comput. C-33 (1984) 323-333.
[5]M. Chan, The distinguishing number of the augmented cube and hyper-cube powers, Discrete Math. 308 (2008) 2330-2336.
[6]H. C. Chan, J. M. Chang, Y. L. Wang and S. J. Horng, Geodes-ic-pancyclicity and fault-tolerant panconnectivity of augmented cubes, Appl. Math. Comput. 207 (2009) 333-339.
[7]S. A. Choudum and V. Sunitha, Augmented cubes, Networks 40 (2002) 71-84.
[8]T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 3rd Ed., MIT Press, Cambridge, Massachusetts, 2009.
[9]P. Cull and S. M. Larson, The Möbius cubes, IEEE Trans. Comput. 44 (1995) 647-659.
[10]D. Z. Du and F. K. Hwang, Generalized de Bruijn digraphs, Networks 18 (1988) 27-38.
[11]K. Efe, The crossed cube architecture for parallel computing, IEEE Trans. Parallel Distribut. Syst. 3 (1992) 513-524.
[12]J.S. Fu, Edge-fault-tolerant vertex-pancyclicity of augmented cubes, Information Processing Letters, 110 (2010) 439-443.
[13]J.S. Fu, Optimal edge-fault-tolerant vertex-pancyclicity of aug-mented cubes, Lecture Notes in Engineering and Computer Sci-ence 2188 (2011) 217-222.
[14]P. A. J. Hilbers, M. R. J. Koopman and J. L. A. van de Snepscheut, The twisted cube, in: J. deBakker, A. Numan, P. Trelearen (Eds.), PARLE: Parallel Architectures and Languages Europe, Parallel Architectures, vol. 1, Springer, Berlin, 1987, pp. 152-158.
[15]S. Y. Hsieh and J. Y. Shiu, Cycle embedding of augmented cubes, Appl. Math. Comput. 191 (2007) 314-319.
[16]S. Y. Hsieh and C. J. Tu, Constructing edge-disjoint spanning trees in locally twisted cubes, Theoret. Comput. Sci. 410 (2009) 926-932.
[17]H. C. Hsu, L. C. Chiang, Jimmy J. M. Tan and L. H. Hsu, Fault hamiltonicity of augmented cubes, Parallel Comput. 31 (2005) 131-145.

[18]H. C. Hsu, P. L Lai and C. H. Tsai, Geodesic pancyclicity and balanced pancyclicity of augmented cubes, Inform. process. Lett. 101 (2007) 227-232.
[19]R. W. Hung and M. S. Chang, Solving the path cover problem on circu-lar-arc graphs by using an approximation algorithm, Discrete Appl. Math. 154 (2006) 76-105.
[20]R. W. Hung and M. S. Chang, Finding a minimum path cover of a dis-tance-hereditary graph in polynomial time, Discrete Appl. Math. 155 (2007) 2242-2256.
[21]R. W. Hung, Constructing two edge-disjoint Hamiltonian cycles and two-equal path cover in augmented cubes, IAENG International Journal of Computer Science 39(1) (2012) 42-49.
[22]R. W. Hung, Embedding two edge-disjoint Hamiltonian cycles into lo-cally twisted cubes, Theoret. Comput. Sci. 412 (2011) 4747-4753.
[23]S.Y. Hsieh and Y.R. Cian, Conditional edge-fault Hamiltonicity of augmented cubes Information Sciences 180 (2010) 2596-2617.
[24]A. Kanevsky and C. Feng, On the embedding of cycles in pancake graphs, Parallel Comput. 21 (1995) 923-936.
[25]T.L. Kung, Y.H. Teng, L.H. Hsu, The panpositionable panconnect-edness of augmented cubes, Information Sciences 180 (2010) 3781-3793.
[26]T.L. Kung, Y.K. Shih, T.H. Tsai, and L.H. Hsu, On the double-pancyclicity of augmented cubes, in: IET Conf., 2010, pp. 287-292.
[27]P. L. Lai and H. C. Hsu, The two-equal-disjoint path cover problem of matching composition network, Inform. Process. Lett. 107 (2008) 18-23.
[28]S. Lee and K. G. Shin, Interleaved all-to-all reliable broadcast on meshes and hypercubes, in: Proc. Int. Conf. Parallel Processing, vol. 3, 1990, pp. 110-113.
[29]C. M. Lee, Y. H. Teng, Jimmy J. M. Tan and L. H. Hsu, Embedding Hamiltonian paths in augmented cubes with a required vertex in a fixed position, Comput. Math. Appl. 58 (2009) 1762-1768.
[30]M. Ma, G. Liu and J. M. Xu, Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes, Parallel Comput. 33 (2007) 36-42.
[31]J. H. Park, One-to-one disjoint path covers in recursive circulants, Journal of KISS 30 (2003) 691-698.
[32]J. H. Park, One-to-many disjoint path covers in a graph with faulty elements, in: Proc. of the International Computing and Combinatorics Conference (COCOON 2004), 2004, pp. 392-401.
[33]J. H. Park, H. C. Kim and H. S. Lim, Many-to-many disjoint path cov-ers in a graph with faulty elements, in: Proc. of the International Symposium on Algorithms and Computation (ISAAC 2004), 2004, pp. 742-753.
[34]V. Petrovic and C. Thomassen, Edge-disjoint Hamiltonian cycles in hypertournaments, J. Graph Theory 51 (2006) 49-52.
[35]Y. Saad and M. H. Schultz, Topological properties of hypercubes, IEEE Trans. Comput. 37 (1988) 867-872.
[36]B. Sosinsky, Networking Bible, Wiley Publishing, Indianapolis, Indiana, 2009.
[37]R. Rowley and B. Bose, Edge-disjoint Hamiltonian cycles in de Bruijn networks, in: Proc. 6th Distributed Memory Computing Conference, 1991, pp. 707-709.
[38]W. W. Wang, M. J. Ma and J. M. Xu, Fault-tolerant pancyclicity of augmented cubes, Inform. Process. Lett. 103 (2007) 52-56.
[39]M. Xu and J. M. Xu, The forwarding indices of augmented cubes, In-form. Process. Lett. 101 (2007) 185-189.