Mc. Heydemann et al., EMBEDDINGS OF HYPERCUBES AND GRIDS INTO DE BRUIJN GRAPHS, Journal of parallel and distributed computing, 23(1), 1994, pp. 104-111
Citations number
9
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
An embedding of a graph G into a graph H is an injective mapping f fro
m the vertices of G into the vertices of H together with a mapping P-f
of edges of G into paths in H. The dilation of the embedding is tile
maximum taken over all the lengths of the paths P-f(xy) associated wit
h the edges xy of G. We show that it is possible to embed a D-dimensio
nal hypercube into the binary de Bruijn graph of the same order and di
ameter with dilation at most [D/2]. Similarly a majority of planar gri
ds can be embedded into a binary de Bruijn graph of the same or nearly
the same order with dilation at most [D/2] where D is the diameter of
the de Bruijn graph. (C) 1994 Academic Press, Inc.