Optimization of Wirelength for Embedding Half Hypercubes into Necklace Graphs

Embedding between two interconnection networks is a technique used to simulate and implement parallel algorithms in parallel processing and computing systems. For an embedding, edge congestion refers to the maximum count of edges of the guest graph being embedded into a single edge of the host graph. Wirelength or layout of an embedding is the sum of congestion on each edge of the host graph. Wirelength problem refers to finding the minimum possible wirelength between two structures of all possible embeddings. Minimizing the wirelength decreases wiring area which in turn reduces the cost and communication delay among the parallel processing components. Properties like regularity and the smaller number of inter-processor connections in hypercube and hypercube variants have made them prominent structures in the field of study and have been explored extensively. The half hypercube, constructed keeping hypercubes as fundamental blocks, exhibits several advantageous properties that are necessary for the effective selection of interconnection networks, such as reduced overhead, symmetry, fewer edges, and a smaller diameter. The paper aims to resolve the wirelength problem of embedding half hypercube to necklace and windmill graphs.