DocumentCode :
1631786
Title :
Fixed layer embeddings of binary trees
Author :
Bein, Wolfgang W. ; Larmore, Lawrence L. ; Shields, Charles ; Sudborough, I. Hal
Author_Institution :
Dept. of Comput. Sci., Nevada Univ., Las Vegas, NV, USA
fYear :
2002
fDate :
6/24/1905 12:00:00 AM
Firstpage :
248
Lastpage :
253
Abstract :
We describe total congestion 1 embeddings of complete binary trees into three dimensional grids with a fixed number of layers. More specifically, we give a one-to-one embedding of any complete binary tree into a hexahedron shaped grid such that no tree nodes or edges occupy the same grid positions. With 7 layers, the number of nodes in the grid is at most 1.09375 times the number of nodes in the tree and with 5 layers we obtain a ratio of 75/64=1.171875. Unlike more standard embeddings these embeddings intricately weave the branches of various subtrees into each other. Finally using a standard recursive method, for 2 layers a ratio of 39/32=1.21875 can be obtained
Keywords :
parallel architectures; trees (mathematics); fixed layer binary tree embeddings; hexahedron shaped grid; one-to-one embedding; parallel architecture; standard recursive method; subtrees; three dimensional grids; Binary trees; Computational modeling; Computer science; Concurrent computing; Dairy products; Hypercubes; Parallel architectures; Particle separators; Tree graphs; Very large scale integration;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Architectures, Algorithms and Networks, 2002. I-SPAN '02. Proceedings. International Symposium on
Conference_Location :
Makati City, Metro Manila
ISSN :
1087-4089
Print_ISBN :
0-7695-1579-7
Type :
conf
DOI :
10.1109/ISPAN.2002.1004295
Filename :
1004295
Link To Document :
بازگشت