✦ LIBER ✦

Embeddings of Hypercubes and Grids into de Bruijn Graphs

✍ Scribed by M.C. Heydemann; J. Opatrny; D. Sotteau

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 644 KB
Volume: 23
Category: Article
ISSN: 0743-7315
DOI: 10.1006/jpdc.1994.1124

No coin nor oath required. For personal study only.

✦ Synopsis

An embedding of a graph (G) into a graph (H) is an injective mapping (f) from 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 the maximum taken over all the lengths of the paths (P_{f}(x y)) associated with the edges (x y) of (G). We show that it is possible to embed a (D)-dimensional hypercube into the binary de Bruijn graph of the same order and diameter with dilation at most ([D / 2]). Similarly a majority of planar grids 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. O 1994 Academic Press. Inc.

📜 SIMILAR VOLUMES

Embedding Cartesian Products of Graphs i

Embedding Cartesian Products of Graphs into de Bruijn Graphs

✍ Thomas Andreae; Michael Nölle; Gerald Schreiber 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 172 KB

## Given a Cartesian product G of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D = D B (n), it is investigated whether or not G is a spanning subgraph of D. Special attention is given to graphs G 1 × • • • × G m which are relevant for parallel computing, namely, to

On Scale Embeddings of Graphs into Hyper

On Scale Embeddings of Graphs into Hypercubes

✍ S.V. Shpectorov 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 492 KB

Hypercubes, shuffle-exchange graphs and

Hypercubes, shuffle-exchange graphs and de Bruijn digraphs

✍ Niall Graham; Frank Harary 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 438 KB

Small congestion embedding of graphs int

Small congestion embedding of graphs into hypercubes

✍ Matsubayashi, Akira; Ueno, Shuichi 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB 👁 1 views

We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hype

Dilation-5 Embedding of 3-Dimensional Gr

Dilation-5 Embedding of 3-Dimensional Grids into Hypercubes

✍ M.Y. Chan; F. Chin; C.N. Chu; W.K. Mak 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 271 KB

We present an algorithm to map the nodes of a 3-dimensional grid to the nodes of its optimal hypercube on a one-to-one basis with dilation at most 5.

Spanners of de Bruijn and Kautz graphs

✍ Rabah Harbane; Carles Padró 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 530 KB