Lower Bounds for Dynamic Tree Embedding in Bipartite Networks

Keqin Li, Yi Pan, Hong Shen, Gilbert H. Young, Si Qing Zheng

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


There are many parallel computations that are tree structured. The structure of a tree is usually unpredictable at compiler-time; the tree grows gradually during the course of a computation. The dynamic tree embedding problem is to distribute the processes of a parallel computation over processors in a parallel computer such that processors perform roughly the same amount of computation, and that communicating processes are assigned to processors that are close to each other. In this paper, we establish lower bounds for the performance ratio of dynamic tree embedding in bipartite static networks, including numerous important networks such asn-dimensional meshes,n-dimensional tori,k-aryn-cubes, cube-connected cycles, and butterflies. Our lower bounds are obtained from both tree and network properties and are applicable to a general class of dynamic tree embedding algorithms.

Original languageEnglish
Pages (from-to)119-143
Number of pages25
JournalJournal of Parallel and Distributed Computing
Issue number2
Publication statusPublished - 15 Sept 1998
Externally publishedYes


  • Bipartite network; dynamic tree embedding; lower bound; performance ratio; randomized tree


Dive into the research topics of 'Lower Bounds for Dynamic Tree Embedding in Bipartite Networks'. Together they form a unique fingerprint.

Cite this