计算机应用 ›› 2016, Vol. 36 ›› Issue (11): 3006-3009.DOI: 10.11772/j.issn.1001-9081.2016.11.3006

• 网络与通信 • 上一篇    下一篇

增广泡型网络的边连通性和限制边连通性

邱亚娜1, 杨玉星1,2   

  1. 1. 河南师范大学 数学与信息科学学院, 河南 新乡 453007;
    2. 大数据统计分析与优化控制河南省工程实验室(河南师范大学), 河南 新乡 453007
  • 收稿日期:2016-04-15 修回日期:2016-07-02 出版日期:2016-11-10 发布日期:2016-11-12
  • 通讯作者: 杨玉星
  • 作者简介:邱亚娜(1990-),女,河南洛阳人,硕士研究生,主要研究方向:组合网络优化;杨玉星(1981-),男,河南商丘人,副教授,博士,CCF会员,主要研究方向:图与组合网络优化。
  • 基金资助:
    国家自然科学基金资助项目(U1304601);河南省教育厅科学技术研究重点项目(14B520004)。

Link connectivity and restricted link connectivity of augmented bubble-sort networks

QIU Yana1, YANG Yuxing1,2   

  1. 1. School of Mathematics and Information Science, Henan Normal University, Xinxiang Henan 453007, China;
    2. Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control(Henan Normal University), Xinxiang Henan 453007, China
  • Received:2016-04-15 Revised:2016-07-02 Online:2016-11-10 Published:2016-11-12
  • Supported by:
    This work is partially supported by the Joint Found of National Natural Science Foundation of China and the Government of Henan Province (U1304601), the Scientific Research Project Fund of Henan Provincial Education Department (14B520004).

摘要: 针对泡型网络边连通度和限制边连通度小、容错能力弱的弊端,采用在泡型网络中增加通信线路的方法构建了高可靠性的增广泡型网络。通过构造最小边割的方法,证实了n维增广泡型网络中去除任意不多于n-1条边时,该增广泡型网络的任意两个节点之间依旧连通;通过构造最小限制边割的方法,证实了在不产生孤立节点的条件下,n维增广泡型网络中去除任意不多于2n-3条边时,该增广泡型网络的任意两个节点之间依旧连通。依据上述结果,通过实例证明增广泡型网络的容错能力优于泡型网络。

关键词: 并行计算机, 高性能网络, 泡型网络, 增广泡型网络, 边连通度, 限制边连通度

Abstract: In view of the disadvantages of small link connectivity, restricted edge connectivity and weak fault tolerance, a kind of augmented bubble-sort network was designed by adding some links to the original bubble-sort network. By constructing a minimum link cut of the n dimensional augmented bubble-sort network, the link connectivity of the n dimensional augmented bubble-sort network was proved to be n, which implied that any two nodes are still connected even deleting n-1 links. The restricted link connectivity of the n dimensional augmented bubble-sort network was proved to be 2n-2. Therefore, any two nodes of the n dimensional augmented bubble-sort network were still connected even deleting 2n-3 links if the removal of these links doesn't result in singletons. Based on above results, the example rusults show that the augmented bubble-sort networks is better than bubble-sort network.

Key words: parallel computer, high-performance interconnection network, bubble-sort network, augmented bubble-sort network, link connectivity, restricted link connectivity

中图分类号: