Maximum subgraph and wirelength optimization in cyclic bipartite networks G k ,3

In parallel computing systems, processors communicate through complex interconnection networks composed of processing nodes and communication links. Efficient data sharing and task execution in such systems depend on optimal module placement, which can be modeled through graph embedding. This work investigates embedding strategies that minimize wirelength when mapping cyclic bipartite networks into tree-like architectures. We also address the maximum subgraph problem (MSP) for cyclic bipartite networks Gk,3 with k≥4, a graph family significant in communication and VLSI design. Furthermore, we present optimal wirelength configurations for embedding Gk,3 into hierarchical topologies such as linear arrays, complete binary trees, sibling trees, and binomial trees. Exact results are obtained for specific cases, while deriving a closed form for the general Gk,m remains an open challenge.