Change search
ReferencesLink to record
Permanent link

Direct link
Embedding Three–Dimensional 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)Conference paper (Refereed)
Abstract [en]

This paper explores the embeddings of multidimensional meshes into minimal Boolean cubes by graph decomposition. 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 the authors 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 {times} 512 {times} 512 mesh.

Place, publisher, year, edition, pages
1990. 319-326 p.
National Category
Computer and Information Science
URN: urn:nbn:se:kth:diva-65526OAI: diva2:483412
The 1990 International Conference on Parallel Processing
NR 20140805Available from: 2012-01-25 Created: 2012-01-25Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Johnsson, Lennart
By organisation
Centre for High Performance Computing, PDC
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

Total: 21 hits
ReferencesLink to record
Permanent link

Direct link