• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Parallel and Distributed Systems >Constructing edge-disjoint spanning trees in product networks
【24h】

Constructing edge-disjoint spanning trees in product networks

机译：在产品网络中构建边缘不相交的生成树

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

摘要

A Cartesian product network is obtained by applying the cross operation on two graphs. We study the problem of constructing the maximum number of edge-disjoint spanning trees (abbreviated to EDSTs) in Cartesian product networks. Let G=(V/sub G/, E/sub G/) be a graph having n/sub 1/ EDSTs and F=(V/sub F/, E/sub F/) be a graph having n/sub 2/ EDSTs. Two methods are proposed for constructing EDSTs in the Cartesian product of G and F, denoted by G/spl times/F. The graph G has t/sub 1/=|E/sub G/|/spl middot/sub 1/(|V/sub G/|-1) more edges than that are necessary for constructing n/sub 1/ EDSTs in it, and the graph F has t2=|E/sub F/'-n/sub 2/(|V/sub F/|-1) more edges than that are necessary for constructing n/sub 2/ EDSTs in it. By assuming that t/sub 1//spl ges/sub 1/ and t/sub 2//spl ges/sub 2/, our first construction shows that n/sub 1/+n/sub 2/ EDSTS can be constructed in G/spl times/F. Our second construction does not need any assumption and it constructs n/sub 1/+n/sub 2/-1 EDSTs in G/spl times/F. By applying the proposed methods, it is easy to construct the maximum numbers of EDSTs in many important Cartesian product networks, such as hypercubes, tori, generalized hypercubes, mesh connected trees, and hyper Petersen networks.
机译：笛卡尔乘积网络是通过对两个图进行交叉运算而获得的。我们研究了在笛卡尔积网络中构造最大数目的边不相交的生成树（缩写为EDST）的问题。令G =（V / sub G /，E / sub G /）是具有n / sub 1 / EDST的图，而F =（V / sub F /，E / sub F /）是具有n / sub 2的图。 / EDST。提出了两种在G和F的笛卡尔积中构建EDST的方法，用G / spl times / F表示。图G的t / sub 1 / = | E / sub G / | / spl middot / n / sub 1 /（| V / sub G / | -1）的边数比构造n / sub 1 / EDST，其中图F比在其中构造n / sub 2 / EDST所需的边缘多t2 = | E / sub F /'-n / sub 2 /（| V / sub F / | -1）个边。它。通过假设t / sub 1 // spl ges / n / sub 1 /和t / sub 2 // spl ges / n / sub 2 /，我们的第一个结构显示n / sub 1 / + n / sub 2 / EDSTS可以以G / spl times / F来构建。我们的第二种构造不需要任何假设，它以G / spl times / F构造n / sub 1 / + n / sub 2 / -1 EDST。通过应用所提出的方法，很容易在许多重要的笛卡尔积网络中构造最大数量的EDST，例如超立方体，花托，广义超立方体，网格连接树和超Petersen网络。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号