Embedding multidimensional grids into optimal hypercubes

作者：Miller Zevi^*; Pritikin Dan; Sudborough I H

来源：Theoretical Computer Science, 2014, 552: 52-82.

DOI：10.1016/j.tcs.2014.07.026

• Embedding
• Dilation
• Hypercube
• Grid

Let G and H be graphs, with vertical bar V(H)vertical bar %26gt;= vertical bar V(G)vertical bar, and f : V(G) -%26gt; V(H) a one to one map of their vertices. Let dilation(f) = max{dist(H)(f(x), f(y)) : xy is an element of E(G)} where dist(H)(v, w) is the distance between vertices v and w of H. Now let B(G, H) = min(f){dilation(f)}, over all such maps f. %26lt;br%26gt;The parameter B(G, H) is a generalization of the classic and well studied %26quot;bandwidth%26quot; of G, defined as B(G, P(n)), where P(n) is the path on n points and n = vertical bar V(G)vertical bar. Let [a(1) x a(2) x ... x a(k)] be the k-dimensional grid graph with integer values 1 through a(i) in the i%26apos;th coordinate. In this paper, we study B(G, H) in the case when G = [a(1) x a(2) x ... x a(k)] and H is the hypercube Q(n) of dimension n = [log(2)(vertical bar V(G)vertical bar)], the hypercube of smallest dimension having at least as many points as G. Our main result is that %26lt;br%26gt;B([a(1) x a(2) x ... x a(k)], Q(n)) %26lt;= 3k, %26lt;br%26gt;provided a(i) %26gt;= 2(22) for each 1 %26lt;= i %26lt;= k. For such G, the bound 3k improves on the previous best upper bound 4k + O(1). Our methods include an application of Knuth%26apos;s result on two-way rounding and of the existence of spanning regular cyclic caterpillars in the hypercube.

• 出版日期2014-10-2