Embeddings of complete binary trees into star graphs with congestion 1
Marie-Claude Heydemann, Jaroslav Opatrný, Dominique Sotteau · 2002
Gives a construction of embeddings of vertex-congestion 1 and dilation 4 of complete binary trees into star graphs. The height of the trees embedded into the n-dimensional star graph S/sub n/ is (n+1)[log/sub 2/ n]-2/sup [log n]+1/+1, which improves the previous result from Bouabdallah and Heydemann (1993, 1994) by more than n/2-1. We then construct embeddings of vertex-congestion 1, dilation at most (5n/4)+2, of complete binary trees into the n-dimensional star graph, whose height differs from the theoretical upper bound of log/sub 2/n! by less than 3[log/sub 2/n]. Our results show that the star networks can efficiently simulate algorithms that are intended for a binary tree architecture.>