计算循环群上4度Bi-Cayley网络直径的快速算法  

Fast algorithm of calculating diameter for Bi-Cayley graph with 4 degrees on cyclic group

作　　者：钟玮[1] 陈宝兴[1] 

机构地区：[1]闽南师范大学计算机学院,福建漳州363000

出　　处：《计算机工程与应用》2015年第14期67-71,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.60973150);福建省自然科学基金(No.2010J01354);闽南师范大学杰青项目(No.MJ13002)

摘　　要：Cayley图是一类高对称正则图,有许多好性质,被广泛认为是一类理想的互连网络拓扑结构。Bi-Cayley图是Cayley图的一个自然推广,特别地,循环群上4度Bi-Cayley网络BC(n;±s1,±s2)是双环网络DLG(n;±s1,±s2)的一个自然推广。讨论了循环群n上4度Bi-Cayley网络BC(n;±s1,±s2)连通的充分必要条件,并给出了计算该网络直径的一种算法,其时间复杂度为O(lb n)。Cayley graph is a kind of high symmetrical regular graph, has many good properties, is widely regarded as a kind of ideal interconnection network topology. Bi-Cayley graph is a natural promotion of Cayley graph, in particular,Bi-Cayley graph BC（n; ±s1, ±s2） with 4 degrees on the cyclic group is a natural extension of double loop network DLG（n; ±s1, ±s2）. This paper discusses the sufficient and necessary conditions of the graph BC（n; ±s1, ±s2） connectivity and gives an algorithm to compute the diameter of BC（n; ±s1, ±s2）, its time complexity is O（lb n）.

关 键 词：CAYLEY图 Bi-Cayley图 直径算法 

分 类 号：O157.9[理学—数学] TP302[理学—基础数学]