| 基于生成树的双环网络G(N;1,s)直径求解算法 |
| |
| 引用本文： | 秦飞,刘明,汤红霞,方木云. 基于生成树的双环网络G(N;1,s)直径求解算法[J]. 微机发展, 2007, 17(11): 57-59 |
| |
| 作者姓名： | 秦飞 刘明 汤红霞 方木云 |
| |
| 作者单位： | 安徽工业大学计算机学院 安徽马鞍山243002 |
| |
| 基金项目： | 国家自然科学基金资助项目(60473142) |
| |
| 摘 要： | 对紧优双环网络G(N;1,s)的直径求解算法做了研究,提出基于生成树的紧优双环网络G(N;1,s)求解算法,给出了双环网络的直径d(N;1,s)公式,对生成树的性质做了研究。利用C#作为编程语言来实现这一算法,并对生成树的结构模型进行了仿真实现。验证了双环网络直径的分布特点:具有最大值、最小值和中间对称性。对任意给定N而2≤s≤N-1的这样一系列双环网络中的所有的紧优双环网络都可以计算出来。该算法的时间复杂度为O(N)。
|
| 关 键 词： | 双环网络 生成树 紧优 |
| 文章编号： | 1673-629X(2007)11-0057-03 |
| 修稿时间： | 2007-01-24 |
Algorithm for Calculating Tight Optimal Double-Loop Networks G(N;1,s) Based on Span-Tree |
| |
| QIN Fei,LIU Ming,TANG Hong-xia,FANG Mu-yun. Algorithm for Calculating Tight Optimal Double-Loop Networks G(N;1,s) Based on Span-Tree[J]. Microcomputer Development, 2007, 17(11): 57-59 |
| |
| Authors: | QIN Fei LIU Ming TANG Hong-xia FANG Mu-yun |
| |
| Abstract: | The algorithm for calculating tight optimal double loop networks G(N;1,s) were studied in this paper.A new method-based on span-tree is presented to calculate the diameter of double-loop networks G(N;1,s).A simple formula for expressing d(N;1,s) of this network is presented.Attributes of the intuitional model-span tree were studied.With C# as program,the algorithm was simulated,and the span tree models were given.The results verify that the diameter of such family of double-loop networks has such characters: maximum values,minimum values and symmetry.The tight optimal double-loop networks in such family,whose N was given randomly and s varied form 2 to N-1,can be calculated.The time complexity of this algorithm is O(N). |
| |
| Keywords: | double-loop networks span tree tight optimal |
| 本文献已被 CNKI 等数据库收录！ |
|
