CFP last date
20 March 2024
Call for Paper
April Edition
IJCA solicits high quality original research papers for the upcoming April edition of the journal. The last date of research paper submission is 20 March 2024

Submit your paper
Know more
Reseach Article

Embedding of C_n^2 and C_(n-1)^2+K_1 in to Arbitrary Tree

by Vijender Kumar, Anil Kumar
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 61 - Number 8
Year of Publication: 2013
Authors: Vijender Kumar, Anil Kumar
10.5120/9950-4597

Vijender Kumar, Anil Kumar . Embedding of C_n^2 and C_(n-1)^2+K_1 in to Arbitrary Tree. International Journal of Computer Applications. 61, 8 ( January 2013), 27-30. DOI=10.5120/9950-4597

@article{ 10.5120/9950-4597,
author = { Vijender Kumar, Anil Kumar },
title = { Embedding of C_n^2 and C_(n-1)^2+K_1 in to Arbitrary Tree },
journal = { International Journal of Computer Applications },
issue_date = { January 2013 },
volume = { 61 },
number = { 8 },
month = { January },
year = { 2013 },
issn = { 0975-8887 },
pages = { 27-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume61/number8/9950-4597/ },
doi = { 10.5120/9950-4597 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:08:35.568225+05:30
%A Vijender Kumar
%A Anil Kumar
%T Embedding of C_n^2 and C_(n-1)^2+K_1 in to Arbitrary Tree
%J International Journal of Computer Applications
%@ 0975-8887
%V 61
%N 8
%P 27-30
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

We present an approach to find the edge congestion sum and dilation sum forembedding of square of cycle on n vertices, Cn2, and Cn2?1 + K1 into arbitrary tree. The embedding algorithms use a technique based on consecutive label property. Our algorithm calculates edge congestion in linear time.

References
  1. N. Bagherzadeh, M. Dowds, and N. Nassif, Embedding an arbitrary tree into the star graph, IEEE Transactions on Computers 45 (1996).
  2. D. Barth, P. Fragopoulou, and M. C. Heydemann, Uniform emulations of Cartesian-product and Cayley graphs, Discrete Appl Math 116 (2002).
  3. S. Bettayeb, B. Cong, M. Girou, and I. H. Sudborough,Embedding of star networks into hypercubes, IEEE Transact Comput 45 (1996).
  4. S. L. Bezrukov, Embedding complete trees into the hypercube, Discrete Appl Math 110 (2001).
  5. S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Ro¨ttger, and U. P. Schroeder, Embedding of hypercubes into grids, MFCS, 1998, 693–701, (Electronic Edition, Springer, Lecture Notes in Computer Science 1450).
  6. S. L. Bezrukov, J. D. Chavez, L. H. Harper, M. Ro¨ttger, and U. P. Schroeder, The congestion of n-cube layout on a rectangular grid, Discrete Math 213 (2000).
  7. S. Bezrukov, B. Monien, W. Unger, and G. Wechsung, Embedding ladders and caterpillars into the hypercube, Discrete Appl Math 83 (1998).
  8. D. Bienstock, On embedding graphs in trees, J Combin Theory Ser B 49 (1990).
  9. A. Bouabdallah, M. C. Heydemann, J. Opatrny, and D. Sotteau, Embedding complete binary trees into star and pancake graphs, Theory ComputSyst 31 (1998).
  10. R. Caha and V. Koubek, Optimal embeddings of generalized ladders into hypercubes, Discrete Math 233 (2001).
  11. J. D. Chavez and R. Trapp, The cyclic cutwidth of trees,DiscreteAppl Math 87 (1998).
  12. M. Chrobak and W. Rytter, Two results on linear embeddings of complete binary trees, TheoretComputSci 136(1994).
  13. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to algorithms, MIT Press and McGraw-Hill,New York, 2001.
  14. J. Diaz, J. Petit, and M. Serna, A survey of graph layout problems, Comput Surveys 34 (2002).
  15. D. Eichhorn, D. Mubayi, K. O'Bryant, and D. B. West, The edge-bandwidth of theta graphs, J Graph Theory 35 (2000).
  16. M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980.
  17. F. Harary, Graph theory, Narosa Publishing House, New Delhi, 2001.
  18. L. T. Q. Hung, M. M. Syslo, M. L. Weaver, and D. B. West, Bandwidth and density for block graphs, Discrete Math 189 (1998).
  19. M. Klugerman, A. Russell, and R. Sundaram, On Embedding complete graphs into hypercubes, Discrete Math 186(1998).
  20. Y. L. Lai and K. Williams, A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J Graph Theory 31 (1999).
  21. T. F. Leighton, Introduction to parallel algorithms and architecture: Arrays, trees, hypercubes, Morgan Kaufmann Publishers, San Mateo, CA, 1992.
  22. A. Matsubayashi and S. Ueno, Small congestion Embedding of graphs into hypercubes, Networks 33 (1999).
  23. J. Opatrny and D. Sotteau, Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1, Discrete Appl Math 98 (2000).
  24. J. Quadras, Embeddings and interconnection networks, Ph. D. Thesis, Department of Mathematics, Loyola College, India.
  25. M. Rottger and U. P. Schroeder, Efficient embeddings of grids into grids, Discrete Appl Math 108 (2001).
  26. H. Schro¨der, O. Sykora, and I. Vrto, Cyclic cutwidth of the mesh, SOF-SEM'99: Theory and practice of informatics (Milovy), 443–452, Lecture Notes in Computer Science 1725, Springer, Berlin, 1999.
  27. S. Simonson and I. H. Sudborough, On the complexity of tree embedding problems, Informat Process Lett 44 (1992).
  28. Y. C. Tseng, Y. S. Chen, T. Y. Juang, and C. J. Chang, Congestion-free, dilation-2 embedding of complete binary trees into star graphs, Networks 33 (1999).
  29. I. Vrto, Cutwidth of the r-dimensional mesh of d-ary trees, Theor Inform Appl 34 (2000), 515–519.
  30. Indra Rajasingh and Albert William, JasinthaQuadras and Paul Manuel, Embedding of Cycles and Wheels into Arbitrary Trees, NetworksVol. 44(3),2004
  31. Indra Rajasingh, BharatiRajan, RamanathanSundaraRajan, On Embedding of m-Sequential k-ary Trees into Hypercubes*,Applied Mathematics, 2010, 3.
Index Terms

Computer Science
Information Sciences

Keywords

Embedding dilation congestion cycles wheel