Embedding of Hypercube into Cylinder

2015/11/25 by Weixing Ji, Ji, Weixing, Qinghui Liu +5
Computer Science · Engineering · #FOS: Computer and information sciences #G.2 #Graphics (cs.GR) #Interconnection Networks and Systems #Parallel Computing and Optimization Techniques #VLSI and FPGA Design Techniques

paper · pdf · doi:10.48550/arxiv.1511.07932

openalex publication_date 2015/11/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Task mapping in modern high performance parallel computers can be modeled as a graph embedding problem, which simulates the mapping as embedding one graph into another and try to find the minimum wirelength for the mapping. Though embedding problems have been considered for several regular graphs, such as hypercubes into grids, binary trees into grids, et al, it is still an open problem for hypercubes into cylinders. In this paper, we consider the problem of embedding hypercubes into cylinders to minimize the wirelength. We obtain the exact wirelength formula of embedding hypercube Q^r into cylinder C_2³× P_2^r-3 with r≥3.

Related

• Embedding hypercubes into torus and Cartesian product of paths and cycles for minimizing wirelength
• Efficient proper embedding of a daisy cube
• Embedding complete multi-partite graphs into Cartesian product of paths and cycles
• Embedding onto Wheel-like Networks
• Embeddings into the Pancake Interconnection Network