Compressing grids into small hypercubes
Zevi Miller, Ivan Hal Sudborough · Networks · 1994
Abstract Let G be a graph, and denote by Q(G)/2t the hypercube of dimension ⌈log2|G|⌉ − t. Motivated by the problem of simulating large grids by small hypercubes, we construct maps f:G → Q(G)/2t, t ⩾ 1, when G is any 2‐ or 3‐dimensional grid, with a view to minimizing communication delay and optimizing distribution of G‐processors in Q(G)/2t, Let dilation(f) = max {dist(f(x), f(y)): xyε(G)}, where “dist” denotes distance in the image network Q(G)/2t, and let the load factor of f be the maximum value of >f−1(h)| over all vertices hε(G)/2t. Our main results are the following: (1) Let G be any 2‐dimensional grid. Then, for any t ⩾ 1, there is a map f :G → Q(G)/2t having dilation 1 and load factor at most 1 + 2t. (2) Given certain upper bounds on the “densities” |G|/|Q(G)/4| or |G|/|Q(G)/8| of G in Q(G)/4 or Q(G)/8, respectively, we get dilation 1 maps f:G → Q(G)/4 or f:G → Q(G)/8 with improved (i.e., smaller) load factor over that given in (1). (3) Let G be any 3‐dimensional grid. Then, there is a map f:G → Q(G)/2 of dilation at most 2 and load factor at most 3, and a map f:G → Q(G)/4 of dilation at most 3 and load factor at most 5.