Old Web
Congestion-free dilation-2 embedding of full binary trees on star graphs
1996
In this paper we present a scheme for congestion-free embedding of full binary trees on a star graph. The height of the tree that can be embedded with this scheme in an n-star is (n+1)[log/sub 2/n]-2/sup [log2n]+1/+1. The dilation of the embedding is two. This is an improvement by a factor of two over an earlier result.
Keywords:
- Parallel computing
- Discrete mathematics
- Red–black tree
- Optimal binary search tree
- Computer science
- Weight-balanced tree
- Threaded binary tree
- Self-balancing binary search tree
- Ternary search tree
- Tree rotation
- Random binary tree
- Theoretical computer science
- Combinatorics
- K-ary tree
- Graph embedding
- Star (graph theory)
- Binary search tree
- Tree (graph theory)
- Binary tree
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
1
Citations
NaN
KQI