Sökning: onr:"swepub:oai:DiVA.org:kth-91011" >
Embedding Meshes in...
-
Ho, Ching-Tien
(författare)
Embedding Meshes in Boolean Cubes by Graph Decomposition
- Artikel/kapitelEngelska1990
Förlag, utgivningsår, omfång ...
-
Elsevier BV,1990
-
printrdacarrier
Nummerbeteckningar
-
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
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:ref swepub-contenttype
-
Ämneskategori:art swepub-publicationtype
Anmärkningar
-
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.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Johnsson, LennartKTH,Parallelldatorcentrum, PDC(Swepub:kth)u1x9yl3z
(författare)
-
KTHParallelldatorcentrum, PDC
(creator_code:org_t)
Sammanhörande titlar
-
Ingår i:Parallel Computing: Elsevier BV8:4, s. 325-3390167-81911872-7336
-
Ingår i:Journal of Parallel and Distributed Computing: Elsevier BV8:4, s. 325-3390743-7315
Internetlänk
Hitta via bibliotek
Till lärosätets databas