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

计算机工程与应用 ›› 2015, Vol. 51 ›› Issue (14): 67-71.

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

钟玮，陈宝兴

闽南师范大学计算机学院，福建漳州 363000

出版日期:2015-07-15 发布日期:2015-08-03

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

ZHONG Wei, CHEN Baoxing

College of Computer Science and Engineering, Minnan Normal University, Zhangzhou, Fujian 363000, China

Online:2015-07-15 Published:2015-08-03

摘要/Abstract

摘要： 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图, Bi-Cayley图, 直径算法

Abstract: 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)].

Key words: Cayley graph, Bi-Cayley graph, diameter algorithm

钟玮，陈宝兴. 计算循环群上4度Bi-Cayley网络直径的快速算法[J]. 计算机工程与应用, 2015, 51(14): 67-71.

ZHONG Wei, CHEN Baoxing. Fast algorithm of calculating diameter for Bi-Cayley graph with 4 degrees on cyclic group[J]. Computer Engineering and Applications, 2015, 51(14): 67-71.

[1]	钟玮1，2，刘日华3，陈宝兴1，2. 一类特殊三维六度环面网络的直径公式[J]. 计算机工程与应用, 2019, 55(13): 119-122.
[2]	魏长明¹，刘浩²，张连明^1，2. 小世界网络的Cayley图模型[J]. 计算机工程与应用, 2009, 45(28): 99-101.