步长有限制的双环网络的最优路由算法

摘要：

双环网络G(n;h)(n是结点数,1和 h是步长)是重要的互联网络结构.目前人们已提出了几种最优路由算法,其时间复杂性至少为O(n).该文考虑步长h有限制的双环网络G(n;h)的最优路由问题,证明了当h满足某个不等式时,可得到G(n;h)的直径显公式和常数时间的最优路由算法,确切地说,至多只要 6次算术运算或比较即可确定源结点0到任一个目标结点的最短路.这些结果可应用于66族紧优和30族几乎紧优双环网络的无限族,使得对于5≤n≤300的每个n (n =99和187除外),都有G(n;h)含于上述某个无限族中.

关键词：双环网络、路由、直径、步长、紧优、几乎紧优

所属期刊栏目：27

分类号：TP301(计算技术、计算机技术)

资助基金：福建省自然科学基金F00018

在线出版日期：2004-07-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：596-603