Microsoft Word - Paper 7.docx The Journal of Engineering Research Vol. 11, No. 2 (2014) 79-88 0 On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach A.R. Touzene* and K. Day Department of Computer Science, College of Science, Sultan Qaboos University, P.O. Box 36, Postal Code 123, Al-Khodh, Muscat, Sultanate of Oman. Received 11 December 2013; accepted 15 September 2014 Abstract: In (Ku et al. 2003), the authors have proposed a construction of edge-disjoint spanning trees EDSTs in undirected product networks. Their construction method focuses more on showing the existence of a maximum number (n1+n2-1) of EDSTs in product network of two graphs, where factor graphs have respectively n1 and n2 EDSTs. In this paper, we propose a new systematic and algorithmic approach to construct (n1+n2) directed routed EDST in the product networks. The direction of an edge is added to support bidirectional links in interconnection networks. Our EDSTs can be used straight- forward to develop efficient collective communication algorithms for both models store-and-forward and wormhole. Keywords: Product networks, Directed edge-disjoint spanning trees, Interconnection networks. אאאאאWא  אאאGא    א Wא  א   א א EDSTs  K   א  אא(n1+n2-1)EDST א אאn1n2EDSTsאK   (n1+n2)   EDSTs  א אא  א א   Kא     Kא EDSTsא א א א   אא  א  אKאא אאW،אאא،אאא *Corresponding author’s e-mail: touzene@squ.edu.om A.R. Touzene and K. Day 80 1. Introduction There has been increasing interest over the last two decades in product networks (Day, and Al-Ayyoub 1997; Ku et al. 2003; X and Yang 2007; Imrich et al. 2008; Klavar and Špacapan 2008; Jänicke et al. 2010; Hammack et al. 2011; Chen et al. 2011; Ma et al. 2011; Cheng et al. 2013; Erveš and Žerovnik 2013; Govorčin and Škrekovski 2014). The Cartesian product is a well-known graph operation. When applied to interconnection networks, the Cartesian product operation combines factor networks into a product network. Graph product is an important method to construct bigger graphs, and plays a key role in the design and analysis of networks. A number of spanning trees of a graph are edge-disjoint if no two trees contain the same edge. Edge-Disjoint spanning trees (EDSTs) have many practical applications including enhancing interconnection network fault-tolerance and developing efficient collective communication algorithms in distributed memory parallel computers (Fragopoulo and Akl 1996; Johnsson and Ho 1989; Touzene 2003). In (Ku et al. 2003), the authorshave studied construction of maximum edge-disjoint spanning trees(n1+n2-1) EDSTs in undirected product network of two graphs, where factor graphs have respectively n1 and n2 EDSTs. The presented construction is more about showing the existence of a maximum number of spanning trees. They did not provide a straight-forward algorithmic way for their construction. In this paper, we propose a new systematic and algorithmic approach to construct (n1+n2) directed rooted edge-disjoint spanning tree in product networks. We assume that the factor graphs are connected graphs and have respectively n1 and n2 EDSTs. Directed rooted edge-disjoint spanning trees have been discussed for different graphs such as the n- dimensional hypercube (Johnsson and Ho 1989), k-ary-n-cube (Touzene 2003), star graphs (Fragopoulo and Akl 1996), etc. We assume directed edges: if a and b are two nodes in the graph, the edge (a, b) is different from the edge (b, a). Directed edges support bidirectional links in interconnection networks. The advantage of our method is the direct use of our trees to develop collective communication procedures in product interconnection networks. The remainder of this paper is organized as follows: In Section 2, notations and preliminaries are presented. In Section 3, the construction of edge-disjoint spanning trees in product networks is proposed. In Section 4, we conclude this paper. 2. Notations and Preliminaries The Cartesian product G =G1×G2 of two undirected graphs G1 = (V1, E1) and G2 = (V2, E2) is the undirected graph G = (V, E), where V and E are given by: V= { | x1∈V1 and x2∈V2}, and for any u = and v = in V, (u, v) is an edge in E if, and only if, either (x1, y1) is an edge in E1 and x2 = y2, or (x2, y2) is an edge in E2 and x1 = y1. The edge (u, v) is called a G1-edge if (x1, y1) is an edge in G1, and it is called a G2- edge if (x2, y2) is an edge in E2. x1 is called the G1- component of u and x2 is called the G2- component. In all what follows we consider directed edges in the sense that the edge (u, v) is different from the edge (v, u). 3. Construction of EDSTs in a Product Network Consider two graphs G1= (V1, E1) and G2 = (V1, E1) having the following properties: the graph G1 contains n1 EDST all rooted at x denoted: X1(x), X2(x), … , Xn1(x). Each Xi(x) tree is assumed to be formed of an edge (x, xi), where xi is the ith neighbor of x, and a sub-tree denoted Xi(x)/x rooted at xi that spans all the G1 nodes other than x (Fig. 1.a). The graph G2 contains n2 EDST all rooted at y denoted: Y1(y), Y2(y), … , Yn2(y), Each Yj(y) tree is assumed to be formed of an edge (y, yj), where yj is the jth neighbor of y, and a sub-tree denoted Yj(y)/y rooted at yj that spans all the G2 nodes other than y (figure 1.b). In Fig. 1 (a, b) straight lines correspond to G1- edges and dashed lines correspond to G2-edges. On Directed Edge-Disjoint Spanning Trees in Product Networks An Algorithmic Approach 81 Xi (x/x)yi(y/y) Figure 1.a. ith EDSTXi (x) rooted at x in G1 Figure 1.b. ith EDST Yi (y) at y in G2 and its Xi (x) sub-tree. and its Yj (y)/y sub-tree. In what follows, we fix a specific node in G as a desired root for the EDST to be constructed. We denote by , i = 1,…, n1, the n1 neighbors of in G reached from via G1-edges, and by , j = 1, …, n2, the n2 neighbors of reached from via G2-edges. For a given node x in G1 and a given tree Y in G2, we denote by the tree in G1×G2 obtained by fixing the G1-component to x and following the edges of tree Y in G2. Similarly, denotes the tree in G1×G2 obtained by following the edges of a tree X in G1 while the G2-component is fixed to node y. 3.1 The ST1 and ST2 EDST for G We present a construction algorithm of n1+n2-2 EDST (without using non-tree edges (Ku et al. 2003) for the product graph G: n1-1 EDST for G denoted ST1(i), i = 2.. n1 and n2-1EDST for G denoted ST2(j), j = 2.. n2. 3.2 Construction of ST1(i), for any i 2 ≤ i ≤ n1 1. Connect to its neighbor (see edge labeled 1 in Fig. 2(a)). 2. Attach to the sub-tree (see sub-tree labeled 2 in Fig. 2(a)). 3. Connect to its neighbor (see edge labeled 3 in Fig. 2(a)). 4. To attach the sub-tree (see sub-tree labeled 4 in Fig. 2(a)). 5. To each node in the sub-tree (including its root ) attach the tree (see sub-tree labeled 5 in Fig. 2(a)). 6. Connect each node in the sub- tree (including its root ) to its neighbor (see edge labeled 6 in Fig. 2(a)). 3.3 Construction of the tree ST2(j), j=2, .. n2 1. Connect to its neighbor (see edge labeled 1 in Fig. 2(b)). 2. Attach to the sub-tree (see sub-tree labeled 2 in Fig. 2(b)). 3. Connect to its neighbor (see edge labeled 3 in Fig. 2(b)). 4. To attach the sub-tree (see labeled 4 in Fig. 2(b)). 5. To each node in the sub-tree (including its root ) attach the tree (see sub-tree labeled 5 in Fig. 2(b)). 6. Connect each node in the sub- tree (including its root ) to its neighbor (see edge labeled 6 in figure 2(b)).In figure 2(a, b), straight lines are G1-edges and dashed lines are to G2-edges. Theorem 1: The set {ST1(i), 2 ≤ i ≤ n2}∪{ST2(j), 2 ≤ j ≤ n2} is a family of (n1+n2-2) edge-disjoint panning trees in G = G1×G2. Proof: We show that all the nodes of the product graph are reached in the (n1+n2-2) edge- disjoint spanning tree using different edges. x xi y Y yj A.R. Touzene and K. Day 82 Figure 2. Construction of spanning trees ST1 (i) and ST2 (j). • Case 1: nodes are reached by different G1-edges (, ), i = 2, ..., n1, in the different trees ST1(i) (edges labeled 6 in figure 2(a)). In trees ST2(j), j = 2, ..., n2, these nodes are covered by G2-edges of the sub-trees (edges labeled 2 in Fig. 2(b)). • Case 2: nodes , similar proof as in case 1 (symmetrical). • Case 3: nodes , i = 2, ..., n1 are covered in four different ways: 1. In sub-trees , i = 2, ..., n1 of trees ST1(i) using Y1 tree edges ( labeled 4 Fig. 2(a)). 2. In sub-tree , j = 2, ..., n2 of the trees ST2(j). These nodes are covered using Yj trees edges (j>1), (labeled 5 in Fig. 2(b)). 3. In sub-trees , i = 2, ..., n1of trees ST1(j) using Xi tree edges (labeled 5 in Fig. 2(a)) . 4. In sub-tree j = 2, ..., n2 of the trees ST2(j)using X1treeedges(labeled 4 in Fig. 2(b)). • Case 4: nodes , similar proof as in case 3 (symmetrical). • Case 5: nodes , x ≠ xi , y ≠yjare covered using different G1-edges in sub-trees , i = 2, ..., n1 of trees ST1(i) (sub- tree labeled 5 in Fig. 2(a)). These nodes are covered using G2-edges in the sub-trees , j = 2, ..., n2 in the trees ST2(j) (labeled 5 in Fig. 2(b)). 3.4 The Special T1 and T2 EDSTs for G We present a construction algorithm for the directed EDSTs in the product graph G denoted T1 and T2. 3.5 Construction of T1 1. Connect to its neighbor (see edge labeled 1 in Fig. 3(a)). 2. Attach to the sub-tree (see sub-tree labeled 2 in Fig. 3(a)). 3. Connect to its neighbor (see edge labeled 3 in Fig. 3(a)). 4. To attach the sub-tree (see sub-tree labeled 4 in Fig. 3(a)). 5. To each node , j=1,…,n2in the sub-tree (including its root ) attach the tree (see sub-tree labeled 5 in Fig. 3(a)). 6. Connect each node in the sub- tree (including its root ) to its neighbor (see edge labeled 6 in Fig. 3(a)). < xi,Y1(y0)/y0> 1 < x0, y> 2 6 (b) ST2(j), j=2.. n2 5 3 4 (a) ST1(i), i=2.. n1 1 2 6 5 3 4 On Directed Edge-Disjoint Spanning Trees in Product Networks An Algorithmic Approach 83 < x1,Y1(y0)/y0> 1 < x0, y/y1> < x0, Y1(y0)/y0> < x, y1> 2 6 (b) T2 5 3 4 (a) T1 1 < X1(x0)/x0, y/yj > 2 6 5 3 4 < x/x1, yj > < x/xi, y1> 7 7 Figure 3. Construction of spanning trees T1 and T2. 7. Connect each node in the sub- tree (including its root ) to its neighbor (see edge labeled 6 in Fig. 3(a)). 8. Connect each node in the sub- tree to the node (see label 7 in Fig. 3(a)). 3.6 Construction of the Tree T2 1. Connect to its neighbor (see edge labeled 1 in Fig. 3(b)). 2. Attach to the sub-tree (see sub-tree labeled 2 in Fig. 3(b)). 3. Connect to its neighbor (see edge labeled 3 in Fig. 3(b)). 4. To attach the sub-tree (see labeled 4 in Fig. 3(b)). 5. To each node , i=1,…,n1in the sub-tree (including its root ) attach the tree (see sub-tree labeled 5 in Fig. 3(b)). 6. Connect each node in the sub- tree (including its root ) to its neighbor . 7. Connect each node in the sub- tree to the node (see label 7 in Fig. 3(b)). Note that in T1 the edges (, ) are used but in T2(j), 2 ≤ j ≤ n2 , the opposite direction edges () , ) are use. Similarly, in T2 the edges (, ) are used but in T1(i), 2 ≤ i ≤ n1 , the opposite direction edges (, ) are used. It is easy to see that using a similar proof as in Theorem 1, the trees T1 , T2 , ST1(i), 2 ≤ i ≤ n2 and T2(j), 2 ≤ j ≤ n2 is a family of (n1+n2) directed rooted edge-disjoint spanning trees in G = G1×G2. To illustrate our construction algorithm, we give a complete example of product of two interconnection networks the 3-cube (3 directed rooted EDTS’s (Johnsson and Ho 1989)) and a ring with three nodes (a, b and c) (2 directed rooted EDST’s). Dark circles represents the root node of the trees and the numbers on the edges A.R. Touzene and K. Day 84 Figure 4. Three EDSTs of the 3-cube and two EDSTs of the ring (3 nodes). Y2 Y1 a b c a c b On Directed Edge-Disjoint Spanning Trees in Product Networks An Algorithmic Approach 85 Figure 5 (a).Spanning Tree ST1(1). Figure 5 (b). Spanning Tree ST1(2). A.R. Touzene and K. Day 86 Figure 5 (c). Spanning Tree ST1(3). Figure 5 (d). Spanning Tree ST2(1). On Directed Edge-Disjoint Spanning Trees in Product Networks An Algorithmic Approach 85 Figure 5 (e). Spanning Tree ST2(2). represent the dimension number relative to the 3-cube, see Figs. 4 and 5. The trees are directed from the root nodes to leave nodes. 4. Conclusions In this paper, we presented a new systematic and algorithmic approach to construct n1+n2 (without using non-tree edges) directed rooted edges-disjoint spanning trees for product networks. The previous work on undirected EDSTs of the product networks (Ku et al. 2003) focuses more on the existence of n1+n2-1 but did not provide an explicit algorithmic way for their construction. Our n1+n2 EDSTs can be used straight-forward to develop efficient collective communication algorithms for both models store-and-forward and wormhole using bidirectional links. References Chen M, GuoX, Zhai S (2011), The optimal strong radius and optimal strong diameter of the Cartesian product graphs. Applied Mathematics Letters 24(5):657-660. Cheng CW, Lee CW, Hsieh SY (2013), Conditional edge-fault hamiltonicity of cartesian product graphs. IEEE Transactions on Parallel and Distributed Systems 24 (10):1951-1960. Day K, Al-Ayyoub AE (1997) , The Cross Product of Interconnection Networks. IEEE Trans. Parallel and Distributed Systems 8(2):109-118. Erveš R, Žerovnik J (2013), Mixed fault diameter of Cartesian graph bundles. Discrete Applied Mathematics 161 (12):1726-1733. Fragopoulo P, Akl SG (1996), Edge-disjoint spanning trees on the star network with application to fauttolerance. IEEE Trans. Computers 45(2):174-185. Govorčin J, Škrekovski R (2014) , On the connectivity of Cartesian product of graphs. ArsMathematicaContemporanea 7(2):293- 297. Hammack R, Imrich W, Klavžar S (2011), Handbook of Product Graphs,Discrete Mathematics and Its Applications, Second ed. CRC Press Boca Raton. Imrich W, Klavžar S, Rall DF (2008) , Topics in Graph Theory: Graphs and their Cartesian Product, AK Peters, Ltd., Wellesley, MA. A.R. Touzene and K. Day 88 Jänicke S, Heine C, Hellmuth M, Stadler PF, Scheuermann G (2010), Visualization of graph products. IEEE Transactions on Visualization and Computer Graphics 16(6):1082-1089. Johnsson SL, Ho CT (1989) , Optimal broadcasting and personalized communication in hypercubes. IEEE Trans. Computers 38(9):1249-1268. Klavar S, Špacapan S (2008), On the edge- connectivity of cartesian product graphs. Asian-European Journal of Mathematics 1(1):93-98. Ku S, Wang B , Hung T (2003), Constructing edge-disjoint spanning trees in product networks. IEEE Trans. Parallel and Distributed Systems 14(3):213-221. Ma M,Xu JM, Zhu Q (2011),The menger number of the cartesian product of graphs. Applied Mathematics Letters 24(5):627-629. Touzene A (2004), Optimal all-port collective communication algorithms for the k-ary n- cube interconnection networks. Journal of Systems Architecture 50:221-231. Xu JM, Yang C(2007), Fault diameter of product graphs. Information Processing Letters 102(6):226-228.