Premium
Embedding grids into grids: Techniques for large compression ratios
Author(s) -
Ellis John A.
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199601)27:1<1::aid-net1>3.0.co;2-q
Subject(s) - embedding , dilation (metric space) , grid , compression (physics) , combinatorics , hypercube , integer (computer science) , mathematics , computer science , folding (dsp implementation) , extension (predicate logic) , integer programming , discrete mathematics , algorithm , geometry , physics , artificial intelligence , electrical engineering , thermodynamics , programming language , engineering
We return to the problem of embedding 2‐dimensional ( h × w ) guest grid graphs into 2‐dimensional ( h ′ × w ′) host grid graphs, where w ′ < w , and h ′ is the smallest integer such that hw ≤ h ′ w ′. This 2‐dimensional problem has many applications in computer science including the simulation of one grid of processors by another of different shape. Also, it can likely be applied to more complex problems such as those involving grids of higher dimension and hypercubes. It is already known that optimal dilation, namely two, is always obtainable whenever w/w ′, the compression ratio , is no greater than two. Only a restricted set of problem instances with compression ratios greater than two could previously be solved optimally, with respect to dilation. We introduce two new techniques, called folding with compression and folding with extension . By applying folding with compression, we show that optimal solutions always exist if w ′ ≥ 7h and the remainder of h ′ integer divided by h is no greater than h ′ integer divided by h . This condition includes all instances of the problem for which w/w ′ ≥ h ≥ 7, i.e., all instances for which the compression ratio and h are sufficiently large. There remain instances, among those of intermediate compression ratio, for which we still do not have optimal solutions. We show that some, but not all, of these can be solved by appling folding with extension. © 1996 John Wiley & Sons, Inc.