Open Access   Article Go Back

Embedding of Circulant Networks into Cycle-of-butterfly

L. Packiaraj1 , K. Manoj2

Section:Research Paper, Product Type: Journal Paper
Volume-06 , Issue-11 , Page no. 264-274, Dec-2018

Online published on Dec 31, 2018

Copyright © L. Packiaraj, K. Manoj . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: L. Packiaraj, K. Manoj, “Embedding of Circulant Networks into Cycle-of-butterfly,” International Journal of Computer Sciences and Engineering, Vol.06, Issue.11, pp.264-274, 2018.

MLA Style Citation: L. Packiaraj, K. Manoj "Embedding of Circulant Networks into Cycle-of-butterfly." International Journal of Computer Sciences and Engineering 06.11 (2018): 264-274.

APA Style Citation: L. Packiaraj, K. Manoj, (2018). Embedding of Circulant Networks into Cycle-of-butterfly. International Journal of Computer Sciences and Engineering, 06(11), 264-274.

BibTex Style Citation:
@article{Packiaraj_2018,
author = {L. Packiaraj, K. Manoj},
title = {Embedding of Circulant Networks into Cycle-of-butterfly},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {12 2018},
volume = {06},
Issue = {11},
month = {12},
year = {2018},
issn = {2347-2693},
pages = {264-274},
url = {https://www.ijcseonline.org/full_spl_paper_view.php?paper_id=710},
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
UR - https://www.ijcseonline.org/full_spl_paper_view.php?paper_id=710
TI - Embedding of Circulant Networks into Cycle-of-butterfly
T2 - International Journal of Computer Sciences and Engineering
AU - L. Packiaraj, K. Manoj
PY - 2018
DA - 2018/12/31
PB - IJCSE, Indore, INDIA
SP - 264-274
IS - 11
VL - 06
SN - 2347-2693
ER -

           

Abstract

Circulant networks is one of most popular interconnection networks since it has a simple structure and is easy to implement. Graph embedding is an important parameter to evaluate the quality 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.

Key-Words / Index Term

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

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.