Change search
ReferencesLink to record
Permanent link

Direct link
Embedding Meshes in Boolean Cubes by Graph Decomposition
KTH, School of Computer Science and Communication (CSC), Centres, Centre for High Performance Computing, PDC. (Parallelldatorcentrum)
1990 (English)In: Parallel Computing, ISSN 0167-8191, Vol. 8, no 4, 325-339 p.Article in journal (Refereed) Published
Abstract [en]

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 G1H1 and G2H2. 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.

Place, publisher, year, edition, pages
1990. Vol. 8, no 4, 325-339 p.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-91011DOI: 10.1016/0743-7315(90)90131-OAI: diva2:507677
NR 20140805Available from: 2012-03-05 Created: 2012-03-05Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
In the same journal
Parallel Computing
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 17 hits
ReferencesLink to record
Permanent link

Direct link