Embedding of Circulant Networks Into Cycle-of-butterfly

Authors

  • Packiaraj L Department of Mathematics, National College, Trichy, India
  • Manoj K Department of Mathematics, National College, Trichy, India

Keywords:

Embedding, Congestion, Wirelength, Circulant networks, cycle-of-butterfly

Abstract

Circulant networks is one of most popular interconnection networks since it has a simple structure and •s easy to implement. Graph embedding is an important parameter to evaluate the qual•ty of an interconnection network and wirelength is an important measure of an embedding. In this paper, we embed circulant network into cycle-of-butterfly with minimum wirelength

References

[1] X.Yang, Q.Dong, Y.Y.Tang, Embedding meshes/tori in faulty crossed cubes, Inf Process Lett, Vol. 110, no. 14-15, 559 - 564, 2010.

[2] T. Dvorak, Dense sets and embedding binary trees into hypercubes, Discrete Applied Math-ematics, Vol. 155, no. 4, 506 - 514, 2007.

[3] G.K. Wong, D.A. Coppersmith, A combinatorial problem related to multimodule memory organization, J. Assoc. Comput. Machin., Vol. 21, no. 3, 392 - 401, 1994.

[4] E.T. Boesch, J. Wang, Reliable circulant networks with minimum transmission delay, IEEE Trans. Parallel Distrib. Syst, Vol. 32, no. 12, 1286 - 1291, 1985.

[5] J.C. Bermond, F. Comellas, D.F. Hsu, Distributed loop computer networks, A survey Journal of Parallel and Distributed Computing, Vol. 24, no. 1, 2 - 10, 1995.

[6] R. Beivide, E. Herrada, J.L. Balc azar, A. Arruabarrena, Optimal Distance Networks of Low Degree for Parallel Computers, IEEE Transactions on Computers, Vol. 40, no. 10, 1109 - 1124, 1991.

[7] R.S. Wilkov, Analysis and Design of Reliable Computer Networks, IEEE Trans. Communi-cations, Vol. 20, no. 3, 660 - 678, 1972.

[8] M. Karlin, New binary coding results by circulants, IEEE Transac- tions on Information Theory, Vol. 15, no. 1, 81 - 92, 1969.

[9] J.M. Xu, Topological Structure and Analysis of Interconnection Networks, Kluwer Academic Publishers, 2001.

[10] Y.L. Lai, K. Williams, A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J. Graph Theory, Vol. 31, 75 - 94, 1999.

[11] J. Fan, X. Jia, Embedding meshes into crossed cubes, Information Sciences, Vol. 177, no. 15, 3151 - 3160, 2007.

[12] W.K. Chen, M.F.M. Stallmann, On embedding binary trees into hypercubes, Journal on Parallel and Distributed Computing, Vol. 24, 132 - 138, 1995.

[13] S.L. Bezrukov, Embedding complete trees into the hypercube, Discrete Applied Mathematics, Vol. 110, no. 2-3, 101 - 119, 2001.

[14] J.-F. Fang, K.-C. Lai, Embedding the incomplete hypercube in books, Information Processing Letters, Vol. 96, 1 - 6, 2005.

[15] P.-L. Lai, C.-H. Tsai, Embedding of tori and grids into twisted cubes, Theoretical Computer Science, Vol. 411, no. 40-42, 3763 - 3773, 2010.

[16] Y. Han, J. Fan, S. Zhang, J. Yang, P. Qian, Embedding meshes into locally twisted cubes, Information Sciences, Vol. 180, no. 19, 3794 - 3805, 2010.

[17] R. Caha, V. Koubek, Optimal embeddings of generalized ladders into hypercubes, Discrete Mathematics, Vol. 233, 65 - 83, 2001.

[18] M. Rottger, U.P. Schroeder, Efficient embeddings of grids into grids, Discrete Applied Math-ematics, Vol. 108, no. 1-2, 143 - 173, 2001.

[19] J. Opatrny, D. Sotteau, Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1, Discrete Applied Mathematics, Vol. 98, 237 - 254, 2000.

[20] J.D. Chavez, R. Trapp, The cyclic cutwidth of trees, Discrete Applied Mathematics, Vol. 87, 25 - 32, 1998.

[21] C.-J. Guu, The Circular Wirelength Problem for Hypercubes, Ph.D. dissertation, University of California, Riverside, 1997.

[22] M.-C. Yang, Path embedding in star graphs, Applied Mathematics and Computation, Vol. 207, no. 2, 283 - 291, 2009.

[23] A. Vodopivec, On embeddings of snarks in the torus, Discrete Mathematics, Vol. 308, no. 10, 1847 - 1849, 2008.

[24] I.Rajasingh, J.Quadras, P.Manuel, A.William, Embedding of cycles and wheels into arbitrary trees, Networks, Vol. 44, 173 - 178, 2004.

[25] P.Manuel, I.Rajasingh, B.Rajan, H. Mercy, Exact wirelength of hypercube on a grid, Discrete Appl Math, Vol. 157, no. 7, 1486 - 1495, 2009.

[26] I. Rajasingh, B. Rajan, R.S. Rajan, On embedding of m-sequencial k-ary trees into hyper-cubes, Applied Mathematics, Vol. 1, no. 6, 499 - 503, 2010.

[27] C.-H. Tsai, Embedding of meshes in Mobius cubes, Theoretical Computer Science, Vol. 401, no. 1-3, 181 - 190, 2008.

[28] A.K. Gupta, D. Nelson, H. Wang, Efficient embeddings of ternary trees into hypercubes, Journal of Parallel and Distributed Computing, Vol. 63, no. 6, 619 - 629, 2003.

[29] P. Manuel, Minimum average congestion of enhanced and augmented hypercube into complete binary tree, Discrete Applied Mathematics, Vol. 159, no. 5, 360 - 366, 2010.

[30] I. Rajasingh, P. Manuel, M. Arockiaraj, B. Rajan, Embeddings of circulant networks, Journal of Combinatorial Optimization, Vol. 26(1), 135 - 151, 2013.

[31] P. Manuel, M. Arockiaraj, I. Rajasingh, B. Rajan, Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength, Discrete Applied Mathematics, Vol. 159, no. 17, 2109 - 2116, 2011.

[32] I. Rajasingh, B. Rajan, R.S. Rajan, Embedding of hypercubes into necklace, windmill and snake graphs, Information Processing Letters, Vol. 112, 509 - 515, 2012.

[33] I. Rajasingh, B. Rajan, R.S. Rajan, Embedding of special classes of circulant networks, hypercubes and generalized Petersen graphs, International Journal of ComputerMathematics, Vol. 89, no. 15, 1970 - 1978, 2012.

[34] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. R¨ottger, U.P. Schroeder, Embedding of hyper-cubes into grids, Mortar Fine Control System, 693 - 701, 1998.

[35] Jywe-Fei Fang, The bipancycle-connectivity of the hypercube, Information Sciences, Vol. 178, 4679 - 4687, 2008.

[36] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. R¨ottger, U.P. Schroeder, The congestion of n-cube layout on a rectangular grid, Discrete Mathematics,Vol. 213, 13 - 19, 2000.

[37] S.L. Bezrukov, S.K. Das, R. Els¨asser, An edge-isoperimetric problem for powers of the Pe-tersen graph, Annals of Combinatorics, Vol. 4, 153 - 169, 2000.

[38] L.H. Harper, Global Methods for Combinatorial Isoperimetric Problems, Cambridge Univer-sity Press, 2004.

[39] G.K. Wong, D.A. Coppersmith, A combinatorial problem related to multimodule memory organization,J. Assoc. Comput. Machin, Vol. 21, no. 3, 392 - 401, 1974.

[40] M.R. Garey, D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, San Francisco 1979.

Downloads

Published

2025-11-18

How to Cite

[1]
L. Packiaraj and K. Manoj, “Embedding of Circulant Networks Into Cycle-of-butterfly”, Int. J. Comp. Sci. Eng., vol. 6, no. 11, pp. 264–274, Nov. 2025.

Issue

Vol. 6 No. 11 (2018): IJCSE Special Issue December Edition

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.