Low expansion packings and embeddings of hypercubes into star graphs
Marcelo Moraes de Azevedo, S. Latift, Nader Bagherzadeh · 1996
Let G(/spl kappa/) and H(n) be respectively a /spl kappa/-dimensional and an n-dimensional graph. Packing is a technique by which p/sub /spl kappa// many copies of each G(/spl kappa/), /spl kappa//sub min//spl les//spl kappa//spl les//spl kappa//sub max/, are embedded into H(n). Packings can use H(n) efficiently by assigning independent tasks to the embedded copies of G(/spl kappa/), and are a useful foundation, from which node allocation and task migration strategies can be built. Copies of G(/spl kappa/), packed into H(n) with dilation d/sub base/, can be combined to produce a variable-dilation embedding of G(/spl kappa/+l) into H(n). Such an embedding has dilation d/sub i/ along dimension i of G(/spl kappa/+l), where d/sub i/=d/sub base/ for i/spl les//spl kappa/, and d/sub i/>d/sub base/ for /spl kappa/