Vertex decomposition method for wirelength problem and its applications to enhanced hypercube networks

Vertex decomposition method for wirelength problem and its applications to enhanced hypercube networks

For access to this article, please select a purchase option:

Buy eFirst article PDF
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Your details
Why are you recommending this title?
Select reason:
IET Computers & Digital Techniques — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

In this study, the authors discuss the vertex congestion of any embedding from the guest graph into the host graph and outline a rigorous mathematical method to compute the wirelength of that embedding. Further, they show that the computation of the optimal wirelength depends on finding optimal solutions for another graph partition problem such as edge isoperimetric problem in that guest graph. On the other side, they consider an important variant of the popular hypercube network, the enhanced hypercube, and obtain the nested optimal solutions for the edge isoperimetric problem. As a combined output, they illustrate the authors’ technique by embedding enhanced hypercube into a caterpillar and from that reducing the linear layout of the enhanced hypercube. As another application of their technique, they embed the hypercube as well as the enhanced hypercube on the two rows extended grid structure with optimal wirelength for the first time and showing that the existing edge congestion technique cannot be used to solve this problem.


    1. 1)
      • 1. Lai, Y.L., Williams, K.: ‘A survey of solved problems and applications on bandwidth, edge sum, and profile of graphs’, J. Graph Theory, 1999, 31, pp. 7594.
    2. 2)
      • 2. Opatrny, J., Sotteau, D.: ‘Embeddings of complete binary trees into grids and extended grids with total vertex-congestion 1’, Discrete Appl. Math., 2000, 98, pp. 237254.
    3. 3)
      • 3. Xu, J.M.: ‘Topological structure and analysis of interconnection networks’ (Springer Publishing Company, New York, NY, US, 2001).
    4. 4)
      • 4. Diaz, J.: ‘Graph layout problems’. Proc. Int. Symp. Mathematical Foundations of Computer Science, 2, Prague, Czechoslovakia, August 1992, pp. 1423.
    5. 5)
      • 5. Cai, H., Zheng, V.W., Chang, K.: ‘A comprehensive survey of graph embedding: problems, techniques and applications’, IEEE Trans. Knowl. Data Eng., 2018, 30, pp. 16161637.
    6. 6)
      • 6. Caha, R., Koubek, V.: ‘Optimal embeddings of generalized ladders into hypercubes’, Discrete Math., 2001, 233, pp. 6583.
    7. 7)
      • 7. Harper, L.H.: ‘Global methods for combinatorial isoperimetric problems’ (Cambridge University Press, Cambridge, 2004).
    8. 8)
      • 8. Manuel, P., Rajasingh, I., Rajan, B., et al: ‘Exact wirelength of hypercube on a grid’, Discrete Appl. Math., 2009, 157, (7), pp. 14861495.
    9. 9)
      • 9. Yang, X., Tang, Y.Y, Cao, J.: ‘Embedding torus in hexagonal honeycomb torus’, IET Comput. Digit. Tech., 2008, 2, (2), pp. 8693.
    10. 10)
      • 10. Rajasingh, I., Manuel, P., Rajan, B., et al: ‘Wirelength of hypercubes into certain trees’, Discrete Appl. Math., 2012, 160, pp. 27782786.
    11. 11)
      • 11. Rostami, H., Habibi, J.: ‘Minimum linear arrangement of chord graphs’, Appl. Math. Comput., 2008, 203, pp. 358367.
    12. 12)
      • 12. Arockiaraj, M., Abraham, J., Quadras, J., et al: ‘Linear layout of locally twisted cubes’, Int. J. Comput. Math., 2017, 94, (1), pp. 5665.
    13. 13)
      • 13. Arockiaraj, M., Quadras, J., Rajasingh, I., et al: ‘Embedding hypercubes and folded hypercubes onto Cartesian product of certain trees’, Discrete Optim., 2015, 17, pp. 113.
    14. 14)
      • 14. Rajasingh, I., Rajan, R.S., Parthiban, N., et al: ‘Both way embedding of circulant network into grid’, J. Discret. Algorithms, 2015, 33, pp. 29.
    15. 15)
      • 15. Garey, M.R., Johnson, D.S.: ‘Computers and intractability, a guide to the theory of NP-completeness’ (Freeman, San Francisco, 1979).
    16. 16)
      • 16. Li, F., Zhang, Q., Zhang, W.: ‘Graph partitioning strategy for the topology design of industrial network’, IET Commun., 2007, 1, (6), pp. 11041110.
    17. 17)
      • 17. Rajasingh, I., Arockiaraj, M., Rajan, B., et al: ‘Circular wirelength of generalized Petersen graphs’, J. Inter. Netw., 2011, 12, (4), pp. 319335.
    18. 18)
      • 18. Katseff, H.: ‘Incomplete hypercubes’, IEEE Trans. Comput., 1988, 37, pp. 604608.
    19. 19)
      • 19. Boals, A.J., Gupta, A.K., Sherwani, N.A.: ‘A lower bound on embedding large hypercubes into small hypercubes’, Congr. Numer., 1990, 78, pp. 141151.
    20. 20)
      • 20. Tzeng, N.F., Wei, S.: ‘Enhanced hypercubes’, IEEE Trans. Comput., 1991, 40, pp. 284294.
    21. 21)
      • 21. Rajasingh, I., Arockiaraj, M.: ‘Linear wirelength of folded hypercubes’, Math. Comput. Sci., 2011, 5, pp. 101111.
    22. 22)
      • 22. Manuel, P.: ‘Minimum average congestion of enhanced and augmented hypercubes into complete binary trees’, Discrete Appl. Math., 2011, 159, (5–6), pp. 360366.

Related content

This is a required field
Please enter a valid email address