Open AccessVertex decomposition method for wirelength problem and its applications to enhanced hypercube networks
Author(s) -
Arockiaraj Micheal,
Liu JiaBao,
Shalini Arul Jeya
Publication year - 2019
Publication title -
iet computers and digital techniques
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.219
H-Index - 46
ISSN - 1751-861X
DOI - 10.1049/iet-cdt.2018.5100
Subject(s) - hypercube , embedding , graph partition , computation , computer science , grid network , vertex (graph theory) , mathematical optimization , grid , graph , mathematics , parallel computing , algorithm , theoretical computer science , geometry , artificial intelligence
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.