×

zbMATH — the first resource for mathematics

Minimum average congestion of enhanced and augmented hypercubes into complete binary trees. (English) Zbl 1209.05050
Summary: We study the embedding problem of enhanced and augmented hypercubes into complete binary trees. Using tree traversal techniques, we compute the minimum average edge congestion of enhanced and augmented hypercubes into complete binary trees.

MSC:
05C05 Trees
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barth, D.; Fragopoulou, P.; Heydemann, M.C., Uniform emulations of Cartesian-product and Cayley graphs, Discrete applied mathematics, 116, 37-54, (2002) · Zbl 0991.05053
[2] S.L. Bezrukov, J.D. Chavez, L.H. Harper, M. Röttger, U.P. Schroeder, Embedding of hypercubes into grids, MFCS, 1998, pp. 693-701.
[3] Bezrukov, S.L.; Chavez, J.D.; Harper, L.H.; Röttger, M.; Schroeder, U.P., The congestion of \(n\)-cube layout on a rectangular grid, Discrete mathematics, 213, 13-19, (2000) · Zbl 0953.68115
[4] Bezrukov, S.; Monien, B.; Unger, W.; Wechsung, G., Embedding ladders and caterpillars into the hypercube, Discrete applied mathematics, 83, 21-29, (1998) · Zbl 0906.05019
[5] Bienstock, D., On embedding graphs in trees, Journal of combinatorial theory. series B, 49, 103-136, (1990) · Zbl 0646.05025
[6] Boals, A.J.; Gupta, A.K.; Sherwani, N.A., Incomplete hypercubes: algorithms and embeddings, The journal of supercomputing, 8, 263-294, (1994)
[7] Bouabdallah, A.; Heydemann, M.-C.; Opatrny, J.; Sotteau, D., Embedding complete binary trees into star and pancake graphs, Theory of computing systems, 31, 279-305, (1998) · Zbl 0896.68108
[8] Caha, R.; Koubek, V., Optimal embeddings of generalized ladders into hypercubes, Discrete mathematics, 233, 65-83, (2001) · Zbl 0986.05034
[9] Chavez, J.D.; Trapp, R., The cyclic cutwidth of trees, Discrete applied mathematics, 87, 25-32, (1998) · Zbl 0909.05024
[10] Choudum, S.A.; Sunitha, V., Augmented cubes, Networks, 40, 2, 71-84, (2002) · Zbl 1019.05052
[11] Choudum, S.A.; Usha Rani, R., Complete binary trees in folded and enhanced cubes, Networks, 43, 4, 266-272, (2004) · Zbl 1054.68098
[12] Chrobak, M.; Rytter, W., Two results on linear embeddings of complete binary trees, Theoretical computer science, 136, 507-526, (1994) · Zbl 0877.68085
[13] El-Amawy, A.; Latifi, S., Properties and performance of folded hypercubes, IEEE transactions on parallel and distributed systems, 2, 31-42, (1991)
[14] Garey, M.R.; Johnson, D.S., Computers and intractibility: A guide to the theory of \(\mathit{NP}\)-completeness, (1979), W.H. Freeman and Company
[15] Hsu, Wen-Jing, Fibonacci cubes—a new interconnection topology, IEEE transactions on parallel and distributed systems, 4, 3-12, (1993)
[16] Katseff, H., Incomplete hypercubes, IEEE transactions on computers, 37, 604-608, (1988)
[17] Klugerman, M.; Russell, A.; Sundaram, R., On embedding complete graphs into hypercubes, Discrete mathematics, 186, 289-293, (1998) · Zbl 0956.05035
[18] Lai, Y.L.; Williams, K., A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, Journal of graph theory, 31, 75-94, (1999) · Zbl 0924.05058
[19] Paul Manuel, Indra Rajasingh, Bharati Rajan, Embedding of hypercubes into complete binary trees, in: Proc. 16th Australasian Workshop on Combinatorial Algorithms, Ballarat, Australia, September 18-21, 2005, pp. 457-466.
[20] Manuel, Paul; Rajasingh, Indra; Rajan, Bharati; Mercy, Helda, Exact wirelength of hypercubes on a grid, Discrete applied mathematics, (2008) · Zbl 1179.05113
[21] Matsubayashi, A.; Ueno, S., Small congestion embedding of graphs into hypercubes, Networks, 33, 71-77, (1999) · Zbl 0990.05036
[22] Opartny, J.; Sotteau, D., Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1, Discrete applied mathematics, 98, 3, 237-254, (2000) · Zbl 0949.05016
[23] Rajasingh, Indra; Quadras, Jasintha; Manuel, Paul; William, Albert, Embedding of cycles into arbitrary trees, Networks, 44, 173-178, (2004) · Zbl 1056.05042
[24] Schröder, H.; Sykora, O.; Vrto, I., Cyclic cutwidth of the mesh, (), 443-452
[25] Simonson, S.; Sudborough, I.H., On the complexity of tree embedding problems, Information processing letters, 44, 323-328, (1992) · Zbl 0768.68059
[26] Tzeng, N.F.; Wei, S., Enhanced hypercubes, IEEE transactions on computers, 40, 284-294, (1991)
[27] Xu, J., ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.