## Abstract

We study the problem of dynamic tree embedding in k-partite networks G ^{k} and analyze the performance on inter-partition load distribution of the embedding. We show that, for ring-connected G ^{k} , if the embedding proceeds by taking uni-directional random walk at length randomly chosen from [0, Δ-1], where a is a multiple of k, the best-case performance is achievable at probability √(2πke ^{-k} ), which is much higher than the asymptotically-zero probability at which the worst-case performance may appear. We also show that the same probabilities hold also for fully-connected G ^{k} if the embedding proceeds by taking random walk at length randomly chosen from [2, ∞). When k=2 (bipartite networks), our results show that if we do the embedding under the above random-walk schemes in their corresponding networks, we will have 50 percent chance to achieve the best-case performance. We also analyze the performances for embedding in these two networks in the expected case, and observe an interesting fact that if a ring- or fully-connected G ^{k} contains equal-sized partitions, the expected-case performance matches that in the best case.

Original language | English |
---|---|

Pages | 451-457 |

Number of pages | 7 |

DOIs | |

Publication status | Published - 1997 |

Externally published | Yes |

Event | 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 - Taipei, Taiwan, Province of China Duration: 18 Dec 1997 → 20 Dec 1997 |

### Conference

Conference | 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 |
---|---|

Country/Territory | Taiwan, Province of China |

City | Taipei |

Period | 18/12/97 → 20/12/97 |