首页> 外文期刊>International Journal of Computer Mathematics: Computer Systems Theory >Recursive and parallel constructions of independent spanning trees in alternating group networks
【24h】

Recursive and parallel constructions of independent spanning trees in alternating group networks

机译:交替组网络中独立跨越树的递归和平行结构

获取原文
获取原文并翻译 | 示例
           

摘要

In this paper, we propose a recursive algorithm and a parallel algorithm for constructing independent spanning trees in ANn. The main ideas of the recursive algorithm are to construct large trees from small trees, use triangle breadth-first search (TBFS) to build a frame of an IST, and use breadth-first search (BFS) to link the rest of the nodes. The main ideas of the parallel algorithm are to build frames through TBFS in parallel, and to use the specific rules to link the rest of the nodes in parallel. We prove the correctness of both algorithms for constructing ISTs in AN_n. Both algorithms are accurate; furthermore, the parallel algorithm is more ecient than the recursive algorithm. (An extended abstract of this paper appeared in: Jie-Fu Huang and Sun-Yuan Hsieh Two methods for constructing independent spanning trees in alternating group networks' Proceedings of International Conference on Creative Lifestyle Computing (ICCLC), 2020.)
机译:在本文中,我们提出了一种递归算法和一个平行算法,用于在ANN中构建独立的跨越树。递归算法的主要思想是从小树构建大树,使用三角形广度 - 首先搜索(TBFS)来构建IST的帧,并使用广度第一搜索(BFS)来链接节点的其余部分。并行算法的主要思想是通过TBFS并行构建帧,并使用特定规则并行链接节点的其余部分。我们证明了两种算法在AN_N中构建ists的正确性。这两种算法都是准确的;此外,并行算法比递归算法更好。 (本文的扩展摘要出现在:Jie-Fu Huang和Sun-yuan Hsieh两种方法,用于在交替集团网络的国际创造性生活方式计算会议上建立独立的跨越树(ICCLC),2020年。)

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号