Vertex decomposition method for wirelength problem and its applications to enhanced hypercube networks. Issue 2 (27th November 2018)

• Record Type: Journal Article
• Authors: Arockiaraj, Micheal; Liu, Jia‐Bao; Shalini, Arul Jeya
• Is Part Of: IET computers & digital techniques. Volume 13:Issue 2(2019)
• Page Start: 87
• Page End: 92
• Publication Date: 2018-11-27
• Subjects: graph theory -- computational geometry -- hypercube networks; host graph -- outline -- rigorous mathematical method -- optimal wirelength -- graph partition problem -- edge isoperimetric problem -- guest graph -- popular hypercube network -- nested optimal solutions -- embedding enhanced hypercube -- existing edge congestion technique -- vertex decomposition method -- wirelength problem -- enhanced hypercube networks -- authors study -- vertex congestion; Computers -- Periodicals; Digital electronics -- Periodicals; Computer engineering -- Periodicals; Computer architecture -- Periodicals; Computer organization -- Periodicals; 621.39
• DOI: 10.1049/iet-cdt.2018.5100
• Languages: English
• ISSNs: 1751-8601

Abstract

Abstract : 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.