✦ LIBER ✦

On Scale Embeddings of Graphs into Hypercubes

✍ Scribed by S.V. Shpectorov

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 492 KB
Volume: 14
Category: Article
ISSN: 0195-6698
DOI: 10.1006/eujc.1993.1016

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Embedding Graphs with Bounded Treewidth

Embedding Graphs with Bounded Treewidth into Their Optimal Hypercubes

✍ Volker Heun; Ernst W. Mayr 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 336 KB

Efficient Dynamic Embeddings of Binary T

Efficient Dynamic Embeddings of Binary Trees into Hypercubes

✍ Volker Heun; Ernst W. Mayr 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 255 KB

In this paper, a deterministic algorithm for dynamically embedding binary trees into hypercubes is presented. Because of a known lower bound, any such algorithm must use either randomization or migration, i.e., remapping of tree vertices, to obtain an embedding of trees into hypercubes with small di

Optimal Dynamic Embeddings of Complete B

Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes

✍ Volker Heun; Ernst W. Mayr 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 242 KB

It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube of the same size. Unfortunately, the usual construction of an embedding of a double-rooted complete binary tree into a hypercube does not provide any hint on how this embedding can be extended if each leaf

On the embedding of graphs into graphs w

On the embedding of graphs into graphs with few eigenvalues

✍ Vu, Van H. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 726 KB

A graph is called of type k if it is connected, regular, and has k distinct eigenvalues. For example graphs of type 2 are the complete graphs, while those of type 3 are the strongly regular graphs. We prove that for any positive integer n, every graph can be embedded in n cospectral, non-isomorphic

On the Embedding of a Class of Regular G

On the Embedding of a Class of Regular Graphs in a Faulty Hypercube

✍ Yu-Chee Tseng; Ten-Hwang Lai 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 293 KB