• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Performance Evaluation >Design and analysis of asymptotically optimal randomized tree embedding algorithms in static networks
【24h】

Design and analysis of asymptotically optimal randomized tree embedding algorithms in static networks

机译：静态网络中渐近最优随机树嵌入算法的设计与分析

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The problem of dynamic tree embedding in static networks is studied in this paper. We provide a unified framework for studying the performance of randomized tree embedding algorithms which allow a newly created tree node to take a random walk of short distance to reach a processor nearby. In particular, we propose simple randomized algorithms on several most common and important static networks, including d-dimensional meshes, d-dimensional tori, and hypercubes. It is shown that these algorithms, which have small constant dilation, are asymptotically optimal for embedding healthy trees. Our analysis technique is based on random walks on static networks. Hence, analytical expressions for expected load on all the processors are available.
机译：研究了静态树中动态树嵌入的问题。我们提供了一个统一的框架，用于研究随机树嵌入算法的性能，该算法允许新创建的树节点采取随机的短距离步行方式到达附近的处理器。特别是，我们在几种最常见和最重要的静态网络上提出了简单的随机算法，包括d维网格，d维tori和超立方体。结果表明，这些算法具有较小的常数膨胀，对于嵌入健康树是渐近最优的。我们的分析技术基于静态网络上的随机游动。因此，可以得到所有处理器上预期负载的解析表达式。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号