• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>RSTI >Routage compact optimal dans les (k, r)-constellations
【24h】

Routage compact optimal dans les (k, r)-constellations

机译：（k，r）星座图中的最佳紧凑路由

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

摘要

Fraigniaud et al., (2001) and independently Thorup et al., (2001) show that n-node trees support routing schemes with message headers, node addresses, and routing tables of O(log n) bits. It still open to known if this optimal result can be extended to the tree-width two graphs. The best known routing scheme require O(log2 n) bits (cf. (Peleg, 2000)). In this article, we extend this optimal result to (k, r)-constellations, I.e., K_(2,r)-minor free networks whose bi-connected components are outerplanar by deleting k vertices. For example, (2, 4)-constellations contain trees, outerplanars and more generally all K_(2,4)-minor free networks.%Fraigniaud et al., (2001) et indépendamment Thorup et al, (2001) ont montré que tout arbre à n nœuds possède un schéma de routage de plus courts chemins utilisant des adresses, des en-têtes et des tables de routage de O(log n) bits. Il est ouvert de savoir si ce résultat optimal peut être étendu, ne serait-ce qu 'aux réseaux de largeur arborescente deux dont la meilleure borne connue, due à (Peleg, 2000) est 0(log2 n) bits. Dans cet article, nous étendons ce résultat optimal aux réseaux appelés (k, r)-constellations, c 'est-à-dire aux réseaux ne contenant pas K_(2,r) comme mineur et dont les composantes bi-connexes peuvent être rendues planaire-extérieures par la suppression de k sommets. Par exemple, les (2, 4)-constellations contiennent les arbres, les graphes planaire-extérieurs et plus généralement les graphes sans mineur K_(2,4).
机译：Fraigniaud等人（2001年）和独立的Thorup等人（2001年）表明，n节点树支持带有消息头，节点地址和O（log n）位路由表的路由方案。是否可以将此最佳结果扩展到树宽的两个图，仍然是未知的。最著名的路由方案需要O（log2 n）位（参见（Peleg，2000））。在本文中，通过删除k个顶点，我们将此最佳结果扩展到（k，r）个星座，即K_（2，r）个次要自由网络，其双向连接的分量在外面。例如，（2，4）-星座包含树木，外平面以及更普遍的所有K_（2,4）-次要自由网络。％Fraigniaud等人（2001）和独立的Thorup等人（2001）表明：每一个n节点树都有使用O（log n）位地址，标头和路由表的最短路径路由方案。公开是否可以将这种最佳结果扩展到是否可以扩展到仅由于（Peleg，2000）为0（log2 n）位而最广为人知的界限为2的树宽的网络。在本文中，我们将此最佳结果扩展到称为（k，r）-星座的网络，也就是说，将不包含K_（2，r）作为次要且其双连接分量可以呈现的网络通过移除k个顶点在平面外部。例如，（2，4）-星座图包含树木，平面外部图，更一般地，没有次要K_（2,4）的图。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号