×

Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees. (English) Zbl 1387.68176

Summary: The hypercube network is one of the most popular interconnection networks since it has simple structure and is easy to implement. The folded hypercube is an important variation of the hypercube. Interconnection networks play a major role in the performance of distributed memory multiprocessors and the one primary concern for choosing an appropriate interconnection network is the graph embedding ability. A graph embedding of a guest graph \(G\) into a host graph \(H\) is an injective map on the vertices such that each edge of \(G\) is mapped into a path of \(H\). The wirelength of this embedding is defined to be the sum of the lengths of the paths corresponding to the edges of \(G\). In this paper we embed hypercube and folded hypercube onto Cartesian product of trees such as 1-rooted complete binary tree and path, sibling tree and path to minimize the wirelength.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C05 Trees
05C62 Graph representations (geometric and intersection representations, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Choudum, S. A.; Nahdini, U., Complete binary trees in folded and enhanced cubes, Networks, 43, 4, 266-272 (2004) · Zbl 1054.68098
[2] Lai, Y. L.; Williams, K., A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs, J. Graph Theory, 31, 75-94 (1999) · Zbl 0924.05058
[3] Opatrny, J.; Sotteau, D., Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1, Discrete Appl. Math., 98, 237-254 (2000) · Zbl 0949.05016
[4] Rosenberg, A. L., Graph embeddings 1988: recent breakthroughs, new directions, (VLSI Algorithms and Architectures (Corfu, 1988). VLSI Algorithms and Architectures (Corfu, 1988), Lecture Notes in Computer Science, vol. 319 (1988), Springer: Springer New York), 160-169 · Zbl 0652.68088
[5] Xu, J.-M., Topological Structure and Analysis of Interconnection Networks (2001), Kluwer Academic Publishers · Zbl 1046.68026
[6] Manuel, P.; Rajasingh, I.; Rajan, B.; Mercy, H., Exact wirelength of hypercube on a grid, Discrete Appl. Math., 157, 7, 1486-1495 (2009) · Zbl 1172.05330
[7] Tsai, C.-H., Embedding of meshes in Möbius cubes, Theoret. Comput. Sci., 401, 181-190 (2008) · Zbl 1146.68017
[8] Harper, L. H., Global Methods for Combinatorial Isoperimetric Problems (2004), Cambridge University Press · Zbl 1043.05002
[9] Bezrukov, S. L., Embedding complete trees into the hypercube, Discrete Appl. Math., 110, 101-119 (2001) · Zbl 0980.05022
[10] Bhatt, S. N.; Chung, F. R.K.; Leighton, F. T.; Rosenberg, A. L., Efficient embeddings of trees in hypercubes, SIAM J. Comput., 21, 1, 151-162 (1992) · Zbl 0743.68037
[11] Choudum, S. A.; Raman, I., On embedding subclasses of height-balanced trees in hypercubes, J. Appl. Math., 179, 1333-1347 (2009) · Zbl 1171.68028
[12] Chen, W.-K. K.; Stallmann, M. F.M., On embedding binary trees into hypercubes, J. Parallel Distrib. Comput., 24, 132-138 (1995)
[13] Dvořák, T., Dense sets and embedding binary trees into hypercubes, Discrete Appl. Math., 155, 506-514 (2007) · Zbl 1111.05023
[14] Havel, I., On certain trees in hypercubes, (Topics in Combinatorics and Graph Theory (1990), Physica-Verlag: Physica-Verlag Heidelberg), 353-358 · Zbl 0743.05016
[15] Heun, V.; Mayr, E. W., Optimal dynamic embeddings of complete binary trees into hypercubes, J. Parallel Distrib. Comput., 61, 1110-1125 (2001) · Zbl 0988.68077
[16] Monien, B.; Sudborough, H., Simulating binary trees on hypercubes, (VLSI, Algorithms and Architectures, Proceedings of the 3rd Aegean Workshop on Computing. VLSI, Algorithms and Architectures, Proceedings of the 3rd Aegean Workshop on Computing, Lecture Notes in Computer Science, vol. 319 (1988)), 170-180 · Zbl 0652.68086
[17] Wang, S.-C.; Leu, Y.-R.; Kuo, S.-Y., Distributed fault-tolerant embedding of several topologies in hypercubes, J. Inf. Sci. Eng., 20, 707-732 (2004)
[18] Wu, J.; Fernandez, E. B.; Luo, Y., Embedding of binomial trees in hypercubes with link faults, J. Parallel Distrib. Comput., 16, 59-74 (1998) · Zbl 0911.68154
[19] Bezrukov, S.; Monien, B.; Unger, W.; Wechsung, G., Embedding ladders and caterpillars into the hypercube, Discrete Appl. Math., 83, 21-29 (1998) · Zbl 0906.05019
[20] Caha, R.; Koubek, V., Optimal embeddings of generalized ladders into hypercubes, Discrete Math., 233, 65-83 (2001) · Zbl 0986.05034
[21] Chavez, J. D.; Trapp, R., The cyclic cutwidth of trees, Discrete Appl. Math., 87, 25-32 (1998) · Zbl 0909.05024
[22] Guu, C.-J., The circular wirelength problem for hypercubes (1997), University of California: University of California Riverside, (Ph.D. dissertation)
[23] 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 Math., 213, 13-19 (2000) · Zbl 0953.68115
[24] Rajasingh, I.; Arockiaraj, M.; Rajan, B.; Manuel, P., Minimum wirelength of hypercubes into \(n\)-dimensional grid networks, Inform. Process. Lett., 112, 583-586 (2012) · Zbl 1243.05127
[25] Manuel, P.; Arockiaraj, M.; Rajasingh, I.; Rajan, B., Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength, Discrete Appl. Math., 159, 2109-2116 (2011) · Zbl 1239.05123
[26] Rajasingh, I.; Manuel, P.; Rajan, B.; Arockiaraj, M., Wirelength of hypercubes into certain trees, Discrete Appl. Math., 160, 2778-2786 (2012) · Zbl 1253.68265
[27] Rajasingh, I.; Rajan, B.; Rajan, R. S., On embedding of \(m\)-sequential \(k\)-ary trees into hypercubes, Appl. Math., 1, 6, 499-503 (2010)
[28] Rajasingh, I.; Arockiaraj, M., Linear wirelength of folded hypercubes, Math. Comput. Sci., 5, 101-111 (2011) · Zbl 1254.05133
[29] Katseff, H., Incomplete hypercubes, IEEE Trans. Comput., 37, 604-608 (1988)
[30] Zhu, Q.; Xu, J.-M.; Hou, X.; Xu, M., On reliability of the folded hypercubes, Inform. Sci., 177, 1782-1788 (2007) · Zbl 1115.68034
[31] Harper, L. H., Optimal assignment of numbers to vertices, J. Soc. Ind. Appl. Math., 12, 131-135 (1964) · Zbl 0222.94004
[32] Bezrukov, S. L.; Das, S. K.; Elsässer, R., An edge-isoperimetric problem for powers of the Petersen graph, Ann. Comb., 4, 153-169 (2000) · Zbl 0951.05053
[33] Garey, M. R.; Johnson, D. S., Computers and Intractability, A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039
[34] Boals, A. J.; Gupta, A. K.; Sherwani, N. A., Incomplete hypercubes: Algorithms and embeddings, J. Supercomput., 8, 263-294 (1994)
[35] Chen, H.-L.; Tzeng, N.-F., A boolean expression-based approach for maximum incomplete subcube identification in faulty hypercubes, IEEE Trans. Parallel Distrib. Syst., 8, 1171-1183 (1997)
[37] Arockiaraj, M.; Manuel, P.; Rajasingh, I.; Rajan, B., Wirelength of 1-fault Hamiltonian graphs into wheels and fans, Inform. Process. Lett., 111, 18, 921-925 (2011) · Zbl 1260.68291
[38] Rajasingh, I.; Manuel, P.; Arockiaraj, M.; Rajan, B., Embedding of circulant networks, J. Comb. Optim., 26, 1, 135-151 (2013) · Zbl 1300.90060
[39] Bezrukov, S. L.; Chavez, J. D.; Harper, L. H.; Röttger, M.; Schroeder, U. P., Embedding of hypercubes into grids, (MFCS (1998)), 693-701
[40] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press and McGraw-Hill: MIT Press and McGraw-Hill New York · Zbl 1047.68161
[41] Rajasingh, I.; Quadras, J.; Manuel, P.; William, A., Embedding of cycles and wheels into arbitrary trees, Networks, 44, 173-178 (2004) · Zbl 1056.05042
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.