id:"swepub:oai:DiVA.org:kth-91011"
Sökning: id:"swepub:oai:DiVA.org:kth-91011" > Embedding Meshes in...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Embedding Meshes in Boolean Cubes by Graph Decomposition
- Ho, Ching-Tien (författare)
-
- Johnsson, Lennart (författare)
- KTH,Parallelldatorcentrum, PDC
- (creator_code:org_t)
- Elsevier BV, 1990
- 1990
- Engelska.
- Ingår i: Parallel Computing. - : Elsevier BV. - 0167-8191 .- 1872-7336. ; 8:4, s. 325-339
- Tidskriftsartikel (refereegranskat)
Abstract
Ämnesord
Stäng
- 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
- NATURVETENSKAP -- Data- och informationsvetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- art (ämneskategori)
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Hitta mer i SwePub
- Av författaren/redakt...
- Ho, Ching-Tien
- Johnsson, Lennar ...
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Data och informa ...
- Artiklar i publikationen
- Parallel Computi ...
- Journal of Paral ...
- Av lärosätet
- Kungliga Tekniska Högskolan
Sök utanför SwePub
- Sök vidare i:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
