Search: onr:"swepub:oai:DiVA.org:kth-91011" >
Embedding Meshes in...
Embedding Meshes in Boolean Cubes by Graph Decomposition
- Article/chapterEnglish1990
Publisher, publication year, extent ...
-
Elsevier BV,1990
-
printrdacarrier
Numbers
-
LIBRIS-ID:oai:DiVA.org:kth-91011
-
https://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-91011URI
-
https://doi.org/10.1016/0743-7315(90)90131-8DOI
Supplementary language notes
-
Language:English
-
Summary in:English
Part of subdatabase
Classification
-
Subject category:ref swepub-contenttype
-
Subject category:art swepub-publicationtype
Notes
-
NR 20140805
-
This paper explores the embeddings of multidimensional meshes into minimal Boolean cubes by graph decomposition. The dilation and the congestion of the product graph (G1 × G2) → (H1 × H2) is the maximum of the dilation and congestion for the two embeddings G1 → H1 and G2 → H2. The graph decomposition technique can be used to improve the average dilation and average congestion. The graph decomposition technique combined with some particular two-dimensional embeddings allows for minimal-expansion, dilation-two, congestion-two embeddings of about 87% of all two-dimensional meshes, with a significantly lower average dilation and congestion than by modified line compression. For three-dimensional meshes we show that the graph decomposition technique, together with two three-dimensional mesh embeddings presented in this paper and modified line compression, yields dilation-two embeddings of more than 96% of all three-dimensional meshes contained in a 512 × 512 × 512 mesh. The graph decomposition technique is also used to generalize the embeddings to meshes with wrap-around. The dilation increases by at most one compared to a mesh without wraparound. The expansion is preserved for the majority of meshes, if a wraparound feature is added to the mesh.
Subject headings and genre
Added entries (persons, corporate bodies, meetings, titles ...)
-
Johnsson, LennartKTH,Parallelldatorcentrum, PDC(Swepub:kth)u1x9yl3z
(author)
-
KTHParallelldatorcentrum, PDC
(creator_code:org_t)
Related titles
-
In:Parallel Computing: Elsevier BV8:4, s. 325-3390167-81911872-7336
-
In:Journal of Parallel and Distributed Computing: Elsevier BV8:4, s. 325-3390743-7315
Internet link
Find in a library
To the university's database