Premium
Congestion‐free, dilation‐2 embedding of complete binary trees into star graphs
Author(s) -
Tseng YuChee,
Chen YuhShyan,
Juang TongYing,
Chang ChiouJyu
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199905)33:3<221::aid-net8>3.0.co;2-k
Subject(s) - dilation (metric space) , embedding , mathematics , star (game theory) , combinatorics , binary number , binary tree , binary search tree , discrete mathematics , computer science , arithmetic , artificial intelligence , mathematical analysis
Trees are a common structure to represent the intertask communication pattern of a parallel algorithm. In this paper, we consider the embedding of a complete binary tree in a star graph with the objective of minimizing congestion and dilation. We develop two embeddings: (i) a congestion‐free, dilation‐2, load‐1 embedding of a level‐ p binary tree, and (ii) a congestion‐free, dilation‐2, load‐2 k embedding of a level‐( p + k ) binary tree, into an n ‐dimensional star graph, where $p = \sum^n_{i=2}\lfloor\log i\rfloor = \Omega(n\log n)$ and k is any positive integer. The first result offers a tree of size comparable or superior to existing results, but with less congestion and dilation. The second result provides more flexibility in the embeddable tree sizes compared to existing results. © 1999 John Wiley & Sons, Inc. Networks 33: 221–231, 1999