Email this article On Directed Edge-Disjoint Spanning Trees in Product Networks, An Algorithmic Approach
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 straightforward to develop efficient collective communication algorithms for both models store-and-forward and wormhole.
Keywords
Full Text:
PDFReferences
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.
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 edgeconnectivity 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 ncube 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.
DOI: http://dx.doi.org/10.24200/tjer.vol11iss2pp79-88
Refbacks
- There are currently no refbacks.
Copyright (c) 2017 A.R. Touzene, K. Day
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
TJER 2017-CC BY-ND
This journal and its content is licensed under a Attribution-NoDerivatives 4.0 International.