ONE BY ONE EMBEDDING THE CROSSED HYPERCUBE INTO PANCAKE GRAPH
Résumé
Let G and H be two simple undirected graphs. An embedding of the graph G into the graph H is an injective mapping f from vertices of G to the vertices of H. The dilation of embedding is the maximum distance between f(u), f(v) taken over edges (u, v) of G. The Pancake graph is one as viable interconnection scheme for parallel computers, which has been examined by a number of researchers. The Pancake was proposed as alternatives to the hypercube for interconnecting processors in parallel computer. Some good attractive properties of this interconnection network include: vertex symmetry, small degree, a sub-logarithmic diameter, extendability, and high connectivity (robustness), easy routing and regularity of topology, fault tolerance, extensibility and embeddability of others topologies. In this paper, we give a construction of one by one embedding of dilation 5 of crossed hypercube into Pancake graph.Références
[1]. Akers, S. B., Krishnamurthy, B. (1990).A group-theoretic model for symmetric interconnection networks. IEEE transactions on Computers. Vol. 4, pp. 555-566.
[2]. Aschheim, R., Femmam, S.,Zerarka, M.F. (2012). New “Graphiton” Model: a Computational Discrete Space, Self-Encoded as a Trivalent Graph. Computer and Information Science Journal, Vol. 5, N° 1, pp. 2-12.
[3]. Bouabdallah, A., Heydemann, M.C., Opatrny, J., Sotteau, D. (1998).Embedding complete binary trees into star and pancake graphs. Theory Computer System Journal, pp. 279-305.
[4]. Efe, K. (1992).The crossed cube architecture for parallel computing. IEEE Trans. Parallel Distributed Systems, vol. 3, n° 5, pp. 513-524.
[5]. Fan, J. (2002).Hamilton-connectivity and cycle-embedding of the mobius cubes. Information Processing Letters, Vol. 82, pp. 113-117.
[6]. Fang, W.C., Hsu, C.C. (2000).On the fault-tolerant embedding of complete binary trees in the pancake graph interconnection network. Information Sciences, Elsevier, pp. 191-204.
[7]. Femmam, S., Zerarka, M.F., Benakila, M.I., (2012).New Approach Construction for Wireless Zig Bee Sensor Based on Embedding Pancake Graphs. Networks and Communication Technologies Journal, vol 1, n°1, pp 7-25.
[8]. Heydari, M.H., Sudborough, I.H. (1997). On the diameter of Pancake network. Algorithms Journal pp. 67-94.
[9]. Huang, W.T., Lin, M.Y., Tan, J.M., Hsu, L.H. (2000). Fault-tolerant ring embedding in faulty crossed cubes.World Multiconf.Sys. Cybertetics and Infor. SCI’2000, Vol. IV, pp. 97-102. British
Journal of Mathematics & Computer Science, 2(1): 1-20, 2012.
[10]. Hung,C.N., Hsu, H., Liang, K., Hsu, L. (2003). Ring embedding in faulty pancake graphs. Information Processing Letters, Elsevier, Vol. 86, pp. 271-275.
[11]. Hsieh, S.Y., Chen, G.H., Ho, C.W. (1999).Fault-free Hamilton-cycles in faulty arrangement graphs. IEEE Transactions on Parallel Distribution System, Vol. 10, pp. 223-237.
[12]. Hsieh, S.Y., Chang, N.W. (2006). Hamiltonian path embedding and pancyclicity on the Mobius cube with faulty nodes and faulty edges. IEEE Transactions on Computers, vol. 55, no. 7, pp. 854-863.
[13]. Hsieh, S.Y., Lee, C.W. (2009).Conditional edge-fault hamiltonicity of matching composition networks. IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 4, pp. 581-592.
[14]. Hsieh, S.Y., Lee, C.W. (2010). Pancyclicity of restricted hypercube-like networks under the conditional fault model. SIAM Journal on Discrete Mathematics, vol. 23, no. 4, pp. 2010-2019.
[15]. Hwang, S.C., Chen, G.H. (2000).Cycles in butterfly graphs. Networks Journal, vol. 35, pp. 161-171.
[16]. Kanevsky, A., Feng, C.(1995).On the embedding of cycles in pancake graphs. Parallel Computer Journal, pp. 923-926.
[17]. Kulasinghe, P., Bettayeb, S. (1995). Multiply-Twisted Hypercube with Five or More Dimensions is not Vertex-Transitive. Information Processing Letters, vol. 5, pp. 33-36.
[18]. Lin, C.K., Tan, J.M., Huang, H.M., Hsu, D.F., Hsu, L.H. (2008).Mutually Independent Hamiltonianicity of Pancake Graphs and Star Graphs. International Symposium on Parallel Architectures, Algorithms, and Networks (i-span), pp. 151-158.
[19]. Lin, J.C., Yang, J.S., Hsu, C.C., Chang, J.M. (2010). Independent spanning trees vs edge disjoint spanning trees in locally twisted cubes. Information Processing Letters Journal, Elsevier North-Holland, Inc. Amsterdam, The Netherlands, Vol. 110 Issue 10, pp. 414-419. British Journal of Mathematics & Computer Science, 2(1): 1-20, 2012
[20]. Menn, A., Somani, A.K. (1992). An efficient sorting algorithm for the star graph interconnection network. 19th International Conference In Parallel Computation, Proceeding, Ed. Cambridge University Press.
[21]. Sengupta,A. (2003).On ring embedding in Hypercubes with faulty nodes and links. Information Processing Letters, Elsevier, Vol. 68, pp. 207-214.
[22]. Senoussi, H., Lavault, C. (1997). Embeddings into the pancake interconnection network. High Performance Computing and Grid in Asia Pacific Region, International Conference on High Performance Computing on the Information Superhighway, HPC-Asia '97.
[23]. Qiu, K., Akl, S.G., Stojmenovic, D.I (1991). Data communication and computational geometry on the star interconnection networks.3rd IEEE Symp. On
parallel and Distributed Processing, Proceeding, pp. 125-129.
[24]. Qiu, K. (1992). The star and Pancake interconnection networks: proprieties and algorithms. PhD thesis, Queens University, Kingston, Ontario, Canada.
[2]. Aschheim, R., Femmam, S.,Zerarka, M.F. (2012). New “Graphiton” Model: a Computational Discrete Space, Self-Encoded as a Trivalent Graph. Computer and Information Science Journal, Vol. 5, N° 1, pp. 2-12.
[3]. Bouabdallah, A., Heydemann, M.C., Opatrny, J., Sotteau, D. (1998).Embedding complete binary trees into star and pancake graphs. Theory Computer System Journal, pp. 279-305.
[4]. Efe, K. (1992).The crossed cube architecture for parallel computing. IEEE Trans. Parallel Distributed Systems, vol. 3, n° 5, pp. 513-524.
[5]. Fan, J. (2002).Hamilton-connectivity and cycle-embedding of the mobius cubes. Information Processing Letters, Vol. 82, pp. 113-117.
[6]. Fang, W.C., Hsu, C.C. (2000).On the fault-tolerant embedding of complete binary trees in the pancake graph interconnection network. Information Sciences, Elsevier, pp. 191-204.
[7]. Femmam, S., Zerarka, M.F., Benakila, M.I., (2012).New Approach Construction for Wireless Zig Bee Sensor Based on Embedding Pancake Graphs. Networks and Communication Technologies Journal, vol 1, n°1, pp 7-25.
[8]. Heydari, M.H., Sudborough, I.H. (1997). On the diameter of Pancake network. Algorithms Journal pp. 67-94.
[9]. Huang, W.T., Lin, M.Y., Tan, J.M., Hsu, L.H. (2000). Fault-tolerant ring embedding in faulty crossed cubes.World Multiconf.Sys. Cybertetics and Infor. SCI’2000, Vol. IV, pp. 97-102. British
Journal of Mathematics & Computer Science, 2(1): 1-20, 2012.
[10]. Hung,C.N., Hsu, H., Liang, K., Hsu, L. (2003). Ring embedding in faulty pancake graphs. Information Processing Letters, Elsevier, Vol. 86, pp. 271-275.
[11]. Hsieh, S.Y., Chen, G.H., Ho, C.W. (1999).Fault-free Hamilton-cycles in faulty arrangement graphs. IEEE Transactions on Parallel Distribution System, Vol. 10, pp. 223-237.
[12]. Hsieh, S.Y., Chang, N.W. (2006). Hamiltonian path embedding and pancyclicity on the Mobius cube with faulty nodes and faulty edges. IEEE Transactions on Computers, vol. 55, no. 7, pp. 854-863.
[13]. Hsieh, S.Y., Lee, C.W. (2009).Conditional edge-fault hamiltonicity of matching composition networks. IEEE Transactions on Parallel and Distributed Systems, vol. 20, no. 4, pp. 581-592.
[14]. Hsieh, S.Y., Lee, C.W. (2010). Pancyclicity of restricted hypercube-like networks under the conditional fault model. SIAM Journal on Discrete Mathematics, vol. 23, no. 4, pp. 2010-2019.
[15]. Hwang, S.C., Chen, G.H. (2000).Cycles in butterfly graphs. Networks Journal, vol. 35, pp. 161-171.
[16]. Kanevsky, A., Feng, C.(1995).On the embedding of cycles in pancake graphs. Parallel Computer Journal, pp. 923-926.
[17]. Kulasinghe, P., Bettayeb, S. (1995). Multiply-Twisted Hypercube with Five or More Dimensions is not Vertex-Transitive. Information Processing Letters, vol. 5, pp. 33-36.
[18]. Lin, C.K., Tan, J.M., Huang, H.M., Hsu, D.F., Hsu, L.H. (2008).Mutually Independent Hamiltonianicity of Pancake Graphs and Star Graphs. International Symposium on Parallel Architectures, Algorithms, and Networks (i-span), pp. 151-158.
[19]. Lin, J.C., Yang, J.S., Hsu, C.C., Chang, J.M. (2010). Independent spanning trees vs edge disjoint spanning trees in locally twisted cubes. Information Processing Letters Journal, Elsevier North-Holland, Inc. Amsterdam, The Netherlands, Vol. 110 Issue 10, pp. 414-419. British Journal of Mathematics & Computer Science, 2(1): 1-20, 2012
[20]. Menn, A., Somani, A.K. (1992). An efficient sorting algorithm for the star graph interconnection network. 19th International Conference In Parallel Computation, Proceeding, Ed. Cambridge University Press.
[21]. Sengupta,A. (2003).On ring embedding in Hypercubes with faulty nodes and links. Information Processing Letters, Elsevier, Vol. 68, pp. 207-214.
[22]. Senoussi, H., Lavault, C. (1997). Embeddings into the pancake interconnection network. High Performance Computing and Grid in Asia Pacific Region, International Conference on High Performance Computing on the Information Superhighway, HPC-Asia '97.
[23]. Qiu, K., Akl, S.G., Stojmenovic, D.I (1991). Data communication and computational geometry on the star interconnection networks.3rd IEEE Symp. On
parallel and Distributed Processing, Proceeding, pp. 125-129.
[24]. Qiu, K. (1992). The star and Pancake interconnection networks: proprieties and algorithms. PhD thesis, Queens University, Kingston, Ontario, Canada.
Publiée
2017-02-06
Comment citer
ZERARKA, M.F..
ONE BY ONE EMBEDDING THE CROSSED HYPERCUBE INTO PANCAKE GRAPH.
Courrier du Savoir, [S.l.], v. 22, fév. 2017.
ISSN 1112-3338.
Disponible à l'adresse : >https://revues.univ-biskra.dz/index.php/cds/article/view/1920>. Date de consultation : 20 avr. 2024
Rubrique
Articles
