Embeddings of complete binary trees into star graphs with congestion 1

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...

Full description

Saved in:
Bibliographic Details
Main Authors: Heydemann, M.-C., Opatrny, J., Sotteau, D.
Format: Conference Proceeding
Language:English
Subjects:
Binary trees
Computer science
Iron
Multiprocessor interconnection networks
Parallel algorithms
Partial response channels
Signal to noise ratio
Topology
Tree graphs
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.< >
DOI:10.1109/HICSS.1995.375502