• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of Parallel and Distributed Computing >Improved lower bounds for embedding hypercubes on de Bruijn graphs
【24h】

Improved lower bounds for embedding hypercubes on de Bruijn graphs

机译：在de Bruijn图上嵌入超立方体的改进下界

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

摘要

Hypercubes and grids are well-known graphs, often used as interconnection networks for parallel systems. The de Bruijn graph has many interesting structural properties including a fixed degree for a logarithmic diameter. It is a very good candidate for building interconnection networks, especially for embedded systems. Heydemann, Opatrny and Sotteau studied the problem of embedding hypercubes and grids in the de Bruijn graph. One of the most useful result of this work was to propose a constructive method for embedding an hypercube of dimension n (denoted by H(n)) into the de Bruijn graph B(2, n) with dilation at most [n/2]. The dilation is one of the most important parameter for measuring the quality of an embedding. It is denned as the maximum over all the lengths of the paths linking the images of all the pairs of vertices. A formal definition can be found in [5]. The main result of this note is to prove that the minimal dilation for embedding H(n) in B(2, n) is not less than the greatest divisor of n excluding [n/2]. This result improves considerably the existing lower bounds. Before presenting the technical details, we will first recall some basic results that essentially come from Heydemann et al. [4] and Andreae et al. [1,2].
机译：超立方体和网格是众所周知的图形，通常用作并行系统的互连网络。 de Bruijn图具有许多有趣的结构特性，包括对数直径的固定度。它是构建互连网络（尤其是嵌入式系统）的很好的候选者。 Heydemann，Opatrny和Sotteau研究了在de Bruijn图中嵌入超立方体和网格的问题。这项工作最有用的结果之一是提出一种构造方法，该方法将最大为[n / 2]的尺寸为n（由H（n）表示）的超立方体嵌入到de Bruijn图B（2，n）中。 。膨胀是衡量嵌入质量的最重要参数之一。它被定义为链接所有成对顶点的图像的路径的所有长度上的最大值。一个正式的定义可以在[5]中找到。该注释的主要结果是证明，将H（n）嵌入B（2，n）的最小扩张不小于n的最大除数[n / 2]。该结果大大改善了现有的下界。在介绍技术细节之前，我们将首先回顾一些基本的结果，这些结果基本上来自Heydemann等人。 [4]和Andreae等。 [1,2]。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号