### Paper Menu >>

### Journal Menu >>

Applied Mathematics, 2010, 3, 499-503 doi:10.4236/am.2010.16065 Published Online December 2010 (http://www.SciRP.org/journal/am) Copyright © 2010 SciRes. AM On Embedding of m-Sequential k-ary Trees into Hypercubes* Indra Rajasingh, Bharati Rajan, Ramanathan Sundara Rajan Department of Mat hematics, Loyola College, Chennai, India E-mail: hellosundar@rediffmail.com Received June 25, 2010; revised October 12, 2010; accepted October 18, 2010 Abstract In this paper, we present an algorithm for embedding an m-sequential k-ary tree into its optimal hypercube with dilation at most 2 and prove its correctness. Keywords: Hypercube, Embedding, Dilation, Pre-order Labeling, Hamiltonian Cycle, k-ary Tree 1. Introduction Let G and H be finite graphs with n vertices. VG and VH denote the vertex sets of G and H, respectively. EG and EH denote the edge sets of G and H, respectively. An embedding f of G into H is defined [1] as follows: 1) f is a bijective map from VG VH 2) f is a one-to-one map from EG to ,: f Pfufv , f Pfufvis a path in H be- tween f uand f v. The dilation of an embedding f of G into H is given by =max,: , f dilfPfufvu vEG where , f Pfufv denotes the length of the path f P. Then, the dilation of G into H is defined as ,=mindilGHdilf where the minimum is taken over all embeddings f of G into H. Embedding G into H with minimum dilation is important for network design and for the simulation of one computer architecture by another [2]. Embeddings as mathematical models of parallel com- puting have been discussed extensively in the literature [3,4]. In these models, both the algorithm to be imple- mented and the interconnection network of the parallel computing system are represented by graphs. The im- plementation details are then studied through the embed- ding. A tree is a connected graph that contains no cycles. Trees are the most fundamental graph-theoretic models used in many fields: information theory, automatics clas- sification, data structure and analysis, artificial intelli- gence, design of algorithms, operation research, combi- natorial optimization, theory of electrical networks and design of network [5]. Trees are ubiquitous in computer science. A rooted tree represents a data structure with a hierarchical relationship among its various elements [6]. The most common type of tree is the binary tree. It is so named because each node can have at most two des- cendents. Binary trees are widely used in data structures because they are easily stored, easily manipulated and easily retrieved [5]. A k-ary tree is a rooted tree in which each node has no more than k children. It is also known as a k-way tree. From a computing perspective, trees form an impor- tant class of computational structures. Many operations such as searching and storing can be easily performed on tree data structures. Hence, there is a large literature on embeddings of various kinds of trees into the graphs of interconnection networks [3,7-25]. In particular, embed- dings of binary trees into hypercubes have received spe- cial attention since they naturally arise as the computa- tional structures of algorithms that employ dvide-and- conquer paradigm [12]. Hypercubes are very popular models for paralled computation because of their regularity and the relatively small number of interprocessor connections. The hyper- cube embedding problem is the problem of mapping a communication graph into a hypercube multiprocessor. Hypercubes are known to be able to simulate other structures such as grids and binary trees [3,26]. It has been shown that an arbitrary binary tree can be embed- *This work is su pp or t ed b y DST Pro j ect No. SR/S4/MS: 494/07. I. RAJASINGH ET AL. Copyright © 2010 SciRes. AM 500 ded into a hypercube with constant dilation [26]. In 1984, Havel [9,27] conjectured that a binary tree can be embedded into a k-dimensional hypercube k Q with dilation one if and only if each of its partite sets contains at most 1 2k vertices. In 1985, Bhatt and Ipsen [7] conjectured that a binary tree can be embedded into its optimal hypercube with dilation at most two as well as into its next-to-optimal hypercube with dilation one. As observed in [13], the conjecture of Havel is stronger than those of Bhatt and Ipsen. Though all these problems have been resolved in several special cases, they still remain open for the general case. Monien and Sudborough [14] proved that every binary tree can be embedded into a hypercube with dilation 3 and 1O expansion. Chen and Stallmann [26] proved that a simple linear-time heuristic embeds an arbitrary binary tree into a hypercube with expansion 1 and aver- age dilation no more than 2. Dvořák [15] constructed the embedding of certain classes of binary trees into hyper- cubes based on an iterative embedding into their sub- graphs induced by dense sets. Heun and Mayr [16] proved that arbitrary binary trees can be embedded into hypercubes with dialtion 8. Further, they constructed an embedding of double-rooted complete binary trees into hypercubes [17]. Sunitha [4] constructed an embedding of some hierarchical caterpillars into their optimal hypercube with dilation 2. Choudum et al. [28] proved that subclasses of height-balanced trees can be embedded into hypercubes. Further, they proved that the height-balanced trees and Fibonacci trees can be embedded into hypercubes [6]. Eğecioğlu and Ibel [18] proved that the dynamic k-ary tree can be embedded into its asymptotic hyper- cube. Thus there is a vast literature on embedding trees into hypercubes. In this paper, we define an m-sequential k-ary tree and prove that it can be embedded into its op- timal hypercube with dilation at most 2. 2. Preliminaries In this section, we introduce the labeling hal to label the vertices of the hypercube architecture. We obtain results that enable us to prove the main result of this paper. Definition 1 [5] An r-dimensional hypercube r Q has nodes respesented by all the binary r-tuples with two nodes being adjacent if and only if their corresponding r-tuples differ in exactly one position. The decimal representation of the vertices is the set 0,1, 2,, 21. nFor convenience, we use the symbol 1x instead of x and therefore the set of labels of the vertices is 1, 2,, 2. n Remark 1 Let G be graph with m vertices. The hypercube of dimension 2 log m is called its optimal hypercube, and one of dimension 21 log m is called next-to-optimal. Definition 2 Let r Q be an r-dimensional hypercube. A partial ordering “ ” on r Q is defined by ji QQ if and only if i Q is a subcube of j Q, 1,ij r . The notation jiQQ < shall mean ji QQ and . ij QQ Definition 3 A hamiltonian labeling of hypercub e r Q, denoted by hal, is the labeling of the vertices of r Q defined inductively as follows: Consider the ordering 12 <<<<< ir QQQ Q on r Q. Label vertices of 1 Q as 0 and 1. If () i uVQ is labeled x , then label the unique vertex 1\ ii vVQ VQ adjacent to u as 1 21 i x . Remark 2 The labeling hal is the decimal equivalent of the binary gray code sequence [26]. Definition 4 A hamiltonian cycle is a cycle that visits each node of the graph exactly once. By convention, the trivial graph on a single node is considered to possess a hamiltonian cycle. A graph possessing a hamiltonian cycle is said to be a hamiltonian graph. Theorem 1 The hamiltonian labeling hal of r Q determines a hamiltonian cycle =1,2, ,2,1 r r C in r Q，2.r Proof We prove that hal determines the hamiltonian cycle 1, 2,, 2,1 l in l Q for all ,l.2 rl We prove the result by induction on .r For 2,=r 2=1,2,3,4,1C is a hamiltonian cycle in 2.QAssume that 1 1=1,2,3,,2 ,1 k k C is a hamiltonian cycle in 1. k Q Consider k Q. We observe that 1k Qis a subcube of . k Q Let 1k F denote the other 1k-dimensional subcube contained in . k QBy definition of k Q, ,uv is an edge in 1k Q if and only if , '' uv is an edge in 1k F , where ,' uu and ,' vv are edges in . k QThus =P 1 1,2,3, ,2k is a hamiltonian path in 1k Q implying that 1 =2+ 11,2 + 12,,2 + 12 kk kk P 1 =2,21,,2 +1 kk k is a hamiltonian path in 1k F. Moreover, the vertex labeled 1 2k is adjacent to the vertex labeled 11 212=2 1 kkk . Again the vertex labeled 1 is adjacent to the vertex labeled 211=2. kk Thus 1 11 11 2 ,212,1=1,2,,2 ,21,,2,1 kk' kkkk PP is a hamiltonian cycle in k Q. The following results are easy consequences of Theorem 1 and the hal labeling of vertices of the hypercube. Lemma 1 Let x and y be the hal labeling of vertices u and v in . r QIf m yx 2= for some m, rm 1, then ,=2duv in . r Q Proof Without loss of generality let y x >. Now 11 =2=22= 2121 mmmm m x yxyz z , I. RAJASINGH ET AL. Copyright © 2010 SciRes. AM 501 where z is the label of some vertex w in . r QThus 1 =21,=21 mm x zy z is a solution to the equation =2 . m xy This implies that w is adjacent to both u and v. In other words, ,=2duv in . r Q Lemma 2 Let x and y be the hal labeling of vertices u and v in . r QIf 122= xxy m for some m, 1,mr then 1=),( vud in . r Q Lemma 3 Let 1 and y be the hal labeling of vertices u and v in . r QIf mim y22=1 for some m and i, 1,m,ir then 2=),( vud in . r Q Proof It is straightforward to see that mim y22=1 implies 12= zy im , where m z2= is the label of some vertex w in . r QThus, {=21 ,=2} mi m yzz is a solution to the equation 1=22 . mi m y This implies that w is adjacent to both u and v. In other words, 2=),( vud in . r Q 3. Embedding Algorithm Embeddings with dilation more than one become significant when trees with branch lengths representing time are considered. In this section, we obtain an embedding algorithm and prove its correctness. Definition 5 A rooted tree T is said to be a step-up tree if for every internal node u of T, any two subtrees i T and j T rooted at children of u are ordered in T in such a way that if ij VT VT, then i T lies to the left of j T. See Figure 1. Definition 6 For 2m and 1k, an m-sequential k-ary tree T(m,k) is a step-up tree obtained by recursively growing the root u with k children under the following conditions. (a) The subtrees rooted at the children of u are of sequential order 12 2 22,2 ,2,2,,2 mmmmmk or 12 1 21,2,2, ,2. mmm mk (b) The root of a subtree of order t s2, 20 t, 3s has 1s children which in turn are the roots of subtrees of sequential order 232 1 3,2 ,2 ,,2,2 sst except when =3, =2st and in this case the sequential order is (2, 3). (c) A subtree of order 3 or 4 with v as a root node is isomorphic to one of the graphs shown in Fi gure 2. T 1 T 2 T 3 T k u Figure 1. Step-up tree T with 12 VTVT k VT . v vv vvv Figure 2. A subtree of order 3 or 4 with v as a root node. Remark 3 ),(kmT rooted at u is said to be of Type A or Type B depending whether the subtrees rooted at the children of u are of sequential order 1 (22,2 ,2, mmm 22 2,,2 ) mmk or 12 1 21,2,2, ,2, mmm mk res- pectively. See Figure 3. Remark 4 ),( kmT of Type A has 12 3 km nodes and ),( kmT of Type B has 22 1 mk nodes. In the sequel, we need the following definition of pre-order tree traversal. Definition 7 Let T be a rooted tree. A pre-order labeling of nodes of T is the lab eling of its nodes the first time we visit the nodes in the traversal. See Figure 4. Embedding Algorithm Input: ),(kmT and its optimal hypercube . r Q Algorithm: Label the nodes of T using pre-order labeling and the vertices of the hypercube using hal labeling. Output: Embedding of T into r Q with dilation at most 2. See Figure 5. (a) (b) Figure 3. (a) T (2, 4) of Type A; (b) T (3, 2) of Type B. 1 2 3 4 56 7 8 9 10 11 12 13 14 15 Figure 4. A pre-order labeling of nodes of T. I. RAJASINGH ET AL. Copyright © 2010 SciRes. AM 502 1 2 3 4 56 7 8 9 10 11 12 13 14 15 hal 1 5 4 2 7 3 6 16 15 14 13 1089 11 12 Figure 5. Embedding of T(2, 3) of Type A into Q4. Theorem 2 An m-sequential k-ary tree can be embedded into its optimal hypercube with dilation at most 2. Proof Consider an embedding f of T into r Q using the embedding algorithm, labeling the nodes of T using pre-order labeling and the vertices of the hypercube using hal labeling such that xxf =)(. Let v be an internal node of T with children 12 ,, , p vv v. Let 12 ,, , p TT T be the subtrees rooted at 12 ,,,, p vv v respectively. Since T is a step-up tree, we have 12 . p VT VTVT Suppose that the root of T is u. Then the label of u is 1. Case 1 (v is a child of u): Let )(1,= ii ye , 1.ik By definition of pre-order traversal, 12 1 =2. ii yVTVTVT By definition of m-sequential k-ary tree of Type A, 12 1 12 (3) 34 =22 2222 =2 [122]2=22. i mmmm mi mimi VT VTVT Therefore 12=1 4 im i y and hence by Lemma 2, the edge i e is of dilation 1. Again by definition of m-sequential k-ary tree of Type B, 12 1 12 (1) 1 =21 222 =21221=221. i mmm mi mimii VT VTVT Therefore iim i y22=1 and hence by Lemma 3, the edge i e is of dilation 2. Case 2 (v is not a child of u): Let the label of v be x. Let ),(= ii yxe , 1.ip By definition of pre-order traversal, 12 1 =1. ii yVT VTVTx By definition of m-sequential k-ary tree, 1 12 1 =3 42=2 1. ii i VT VTVT Therefore i ixy 2= and hence by Lemma 1, the edge i e is of dilation 2. 4. Conclusions In this paper, we have obtained an embedding algorithm to embed an m-sequential k-ary tree into its optimal hypercube with dilation at most 2. We have also proved its correctness. This study is important as the embedding of binary trees into hypercubes received special attention in the computational structures of algorithm such as searching and storing. 5. References [1] S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Röttger and U. P. Schroeder, “Embedding of Hypercubes into Grids,” Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science, Brno, 24-28 August 1998 , pp. 693-701. [2] S. L. Bezrukov, B. Monien, W. Unger and G. Wechsung, “Embedding Ladders and Caterpillars into the Hyper- cube,” Discrete Applied Mathematics, Vol. 83, No. 1-3, 1998, pp. 21-29. [3] P. Manuel, I. Rajasingh, B. Rajan and H. Mercy, “Exact Wirelength of Hypercube on a Grid,” Discrete Applied Mathematics, Vol. 157, No. 7, 2009, pp. 1486-1495. [4] V. Sunitha, “Embedding Some Hierarchical Caterpillars into Hypercube,” Electronic Notes in Discrete Mathe- matics, Vol. 22, No. 10, 2005, pp. 387-389. [5] J. M. Xu, “Topological Structure and Analysis of Inter- connection Networks,” Kluwer Academic Publishers, Norwell, 2001. [6] S. A. Choudum and I. Raman, “Embedding Height Ba- lanced Trees and Fibonacci Trees in Hypercubes,” Journal of Applied Mathematics and Computing, Vol. 30, No. 1-2, I. RAJASINGH ET AL. Copyright © 2010 SciRes. AM 503 2009, pp. 39-52. [7] S. N. Bhatt and I. C. Ipsen, “How to Embed Trees in Hypercubes,” Technical Report YALEU/DCS/RR-443, Yale University, Connecticut, 1985. [8] Q. Dong, X. Yang, J. Zhao and Y. Y. Tang,“Embbedding a Family of Disjoint 3D Meshes into a Crossed Cube,” Infor- mation Sciences, Vol. 178, No. 11, 2008, pp. 2396-2405. [9] I. Havel, “On Hamiltonian Circuits and Spanning Trees of Hypercubes,” Casopis.Pest.Mat., Vol. 109, No. 2, 1984, pp. 135- 152. [10] I. Havel and P. Liebl, “O Vnoren Dichotomickeho Stro- mu Do Krychle (in Czech with English summary),” Casopis. Pest. Mat., Vol. 97 , No. 2, 1972, pp. 201-205. [11] L. Nebesky, “On Cubes and Dichotomic Trees,” Casopis. Pest. Mat., Vol. 99, No. 2, 1974, pp. 164-167. [12] D. E. Knuth, “The Art of Computer Programming-3, Sorting and Searching,” Addison-Wesley Publishing Company, Massachusetts, 1973. [13] T. Dvořák, I. Havel, P. Liebl and J.-M. Laborde, “Gene- ralized Hypercubes and Graph Embedding with Dila- tion,” Rostocker Mathematisches Kolloquium, Vol. 39, 1990, pp. 13-20. [14] B. Monien and H. Sudborough, “Simulating Binary Trees on Hypercubes,”VLSI, Algorithms and Architectures, Proceedings of the 3rd Aegean Workshop on Computing, LNCS, Springer-Verlag Vol. 319, No. 24, 1988, pp. 170-180. [15] T. Dvořák, “Dense Sets and Embedding Binary Trees into Hypercubes,”Discrete Applied Mathematics, Vol. 155, No. 4, 2007, pp. 506-514. [16] V. Heun and E. W. Mayr, “A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube,”Journal of Algorithms, Vol. 20, No. 2, 1996, pp. 375-399. [17] V. Heun and E. W. Mayr, “Optimal Dynamic Em- beddings of Complete Binary Trees into Hypercubes,” Journal of Parallel and Distributed Computing, Vol. 61, No. 8, 2001, pp. 1110-1125. [18] O. Eğecioğlu and M. Ibel, “Asymptotic Hypercube Em- beddings of Dynamic k-ary Trees,” Congressus Nume- rantium, Vol. 126, 1997, pp. 21-32. [19] J. Fan and X. Jia, “Embedding Meshes into Crossed Cubes,” Information Sciences, Vol. 177, No. 15, 2007, pp. 3151-3160. [20] J. Fan, X. Jia and X. Lin,“Complete Path Embeddings in Crossed Cubes,” Information Sciences, Vol. 176, No. 22, 2006, pp. 3332-3346. [21] J. S. Fu, “Longest Fault-free Paths in Hypercubes with Vertex Faults,” Information Sciences, Vol. 176, No. 7, 2006, pp. 759-771. [22] I. Havel and P. Liebl,“One-Legged Caterpillars Span Hypercubes,”Journal of Graph Theory, Vol. 10, No. 1, 1986, pp. 69-77. [23] T. C. Lin and D. R. Duh, “Constructing Vertex-Disjoint Paths in (n, k)-star Graphs,”Information Sciences, Vol. 178, No. 3, 2008, pp. 788-801. [24] C. H. Tsai and Y. C. Lai, “Conditional Edge-Fault-Tolerant Edge-Bipancyclicity of Hypercubes,” Information Sciences, Vol. 177, No. 24, 2007, pp. 5590-5597. [25] R. Y. Wu, G. Chen, Y-L. Kuo and G. J. Chang, “Node- disjoint Paths in Hierarchical Hypercube Networks,” Information Sciences, Vol. 177, No. 19, 2007, pp. 4200-4207. [26] W. K. Chen and M. F. M. Stallmann,“On Embedding Binary Trees into Hypercubes,” Journal on Parallel and Distributed Computing, Vol. 24, No. 2, 1995, pp. 132-138. [27] I. Havel, “On Certain Trees in Hypercubes,” In Topics in Combinatorics and Graph Theory, Physica-Verlag, Heidelberg, 1990, pp. 353-358. [28] S. A. Choudum and I. Raman, “On Embedding Subclasses of Height-balanced Trees in Hypercubes,” Journal of Applied Mathematics, Vol. 179, No. 9, 2009, pp. 1333-1347. |