Optimizing Wirelength in Embedding Turán Graphs into Complete Binary Trees
摘要
The development of parallel algorithms and the modeling of interconnection networks can be converted into a graph embedding problem. To measure the quality of an embedding, numerous cost parameters are utilized. The wirelength is one of these elements that is commonly taken into account. In this investigation, we establish that the wirelength achieved by embedding a p-partite Turán graph into a complete binary tree is minimized. Additionally, we calculate the wirelength associated with embedding a 2-partite Turán graph into a complete binary tree through the utilization of congestion. Furthermore, using dilation, we determine the disparity between this wirelength and the wirelength obtained by embedding a complete bipartite graph into a 1-rooted complete binary tree. Subsequently, we establish that the wirelength achieved by embedding a 2-partite Turán graph into a complete binary tree equals the wirelength obtained by embedding a complete bipartite graph into a 1-rooted complete binary tree, with the added condition of introducing a fault in one vertex in both graphs.