|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 2 van 10 gevonden artikelen
| Titel: |
EMBEDDINGS OF COMPLETE BINARY TREES INTO EXTENDED GRIDS WITH EDGE-CONGESTION 1* |
| Auteur: |
Heydemann, M. -C. Sotteau, D. Opatrny, J. |
| Verschenen in: |
International journal of parallel, emergent and distributed systems |
| Paginering: | Jaargang 8 (1996) nr. 3-4 pagina's 333-354 |
| Jaar: |
1996 |
| Inhoud: |
Let G and H be two simple, undirected graphs. An embedding of the graph G into the graph H is an injective mapping f from the vertices of G to the vertices of H, together with a mapping which assigns to each edge [u, v] of G a path between f (u) and f (v) in H. The extended grid EM(r, s) is the graph whose vertex set is the set of pairs on nonnegative integers, {(i, j) : 0 ≤ i < r, 0 ≤ j < s}, in which there is an edge between vertices (i, j) and (k, l) if and only if |I - k| ≤ 1 and |j-l| ≤ 1. In this paper, we give an embedding of any complete binary tree of odd height into its optimal square extended grid. This embedding has edge-congestion 1, dilation 2n-2 + 1, and its average dilation is less than 1.12. We also show that an embedding of a complete binary tree of odd height into its optimal grid, which is obtained from the embedding into the optimal extended grid by a simple transformation, has edge-congestion 2, dilation 22n-1, and it creates in the grid far fewer edges of congestion 2 than the embedding from [9], |
| Uitgever: |
Taylor & Francis |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 2 van 10 gevonden artikelen
| << vorige | volgende >> |