## 摘要

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.

原文 | English |
---|---|

頁面 | 451-457 |

頁數 | 7 |

DOIs | |

出版狀態 | Published - 1997 |

對外發佈 | 是 |

事件 | 3rd International Symposium on Parallel Architectures, Algorithms, and Networks, I-SPAN 1997 - Taipei, Taiwan, Province of China 持續時間: 18 12月 1997 → 20 12月 1997 |

### Conference

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

國家/地區 | Taiwan, Province of China |

城市 | Taipei |

期間 | 18/12/97 → 20/12/97 |