The week's pick
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
- N. Bagherzadeh, M. Dowds, and N. Nassif, Embedding an arbitrary tree into the star graph, IEEE Transactions on Computers 45 (1996).
- D. Barth, P. Fragopoulou, and M. C. Heydemann, Uniform emulations of Cartesian-product and Cayley graphs, Discrete Appl Math 116 (2002).
- S. Bettayeb, B. Cong, M. Girou, and I. H. Sudborough,Embedding of star networks into hypercubes, IEEE Transact Comput 45 (1996).
- S. L. Bezrukov, Embedding complete trees into the hypercube, Discrete Appl Math 110 (2001).
- 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).
- 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).
- S. Bezrukov, B. Monien, W. Unger, and G. Wechsung, Embedding ladders and caterpillars into the hypercube, Discrete Appl Math 83 (1998).
- D. Bienstock, On embedding graphs in trees, J Combin Theory Ser B 49 (1990).
- A. Bouabdallah, M. C. Heydemann, J. Opatrny, and D. Sotteau, Embedding complete binary trees into star and pancake graphs, Theory ComputSyst 31 (1998).
- R. Caha and V. Koubek, Optimal embeddings of generalized ladders into hypercubes, Discrete Math 233 (2001).
- J. D. Chavez and R. Trapp, The cyclic cutwidth of trees,DiscreteAppl Math 87 (1998).
- M. Chrobak and W. Rytter, Two results on linear embeddings of complete binary trees, TheoretComputSci 136(1994).
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,Introduction to algorithms, MIT Press and McGraw-Hill,New York, 2001.
- J. Diaz, J. Petit, and M. Serna, A survey of graph layout problems, Comput Surveys 34 (2002).
- D. Eichhorn, D. Mubayi, K. O'Bryant, and D. B. West, The edge-bandwidth of theta graphs, J Graph Theory 35 (2000).
- M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980.
- F. Harary, Graph theory, Narosa Publishing House, New Delhi, 2001.
- L. T. Q. Hung, M. M. Syslo, M. L. Weaver, and D. B. West, Bandwidth and density for block graphs, Discrete Math 189 (1998).
- M. Klugerman, A. Russell, and R. Sundaram, On Embedding complete graphs into hypercubes, Discrete Math 186(1998).
- 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).
- T. F. Leighton, Introduction to parallel algorithms and architecture: Arrays, trees, hypercubes, Morgan Kaufmann Publishers, San Mateo, CA, 1992.
- A. Matsubayashi and S. Ueno, Small congestion Embedding of graphs into hypercubes, Networks 33 (1999).
- 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).
- J. Quadras, Embeddings and interconnection networks, Ph. D. Thesis, Department of Mathematics, Loyola College, India.
- M. Rottger and U. P. Schroeder, Efficient embeddings of grids into grids, Discrete Appl Math 108 (2001).
- 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.
- S. Simonson and I. H. Sudborough, On the complexity of tree embedding problems, Informat Process Lett 44 (1992).
- 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).
- I. Vrto, Cutwidth of the r-dimensional mesh of d-ary trees, Theor Inform Appl 34 (2000), 515–519.
- Indra Rajasingh and Albert William, JasinthaQuadras and Paul Manuel, Embedding of Cycles and Wheels into Arbitrary Trees, NetworksVol. 44(3),2004
- 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