On the optimal layout of (K p  − C p ) n into grid and certain structures

Abstract

Abstract Interconnection networks constitute complex configurations of processors and communication links that facilitate data transmission between processors in a parallel computing system. Their architecture and design heavily depend on parameters such as wirelength, dilation, bandwidth, and minimum cutwidth. The process of constructing layouts on a board using the necessary modules determines the manufacturing cost in computer networks, where knowledge of graph embedding serves as an integral tool. Placement problems associated with circuit designs, for which no deterministic techniques exist, can be addressed by obtaining the optimal architecture through the embedding function. This article focuses on embedding the guest graph (K p − C p ) n into various host graphs, including the grid, generalized book graph, triangular snake, and variants of the banana tree. Furthermore, their optimal wirelengths are also obtained.

Keywords

• Wirelength
• Maximum subgraph problem
• Graph embedding
• Optimality