四川大学学报（自然科学版）
四川大學學報（自然科學版）
사천대학학보（자연과학판）
JOURNAL OF SICHUAN UNIVERSITY（NATURAL SCIENCE EDITION）
2004年
5期
915-920
,共6页
双连环网%L-形%直径%算法
雙連環網%L-形%直徑%算法
쌍련배망%L-형%직경%산법
Double Loop Network (DLN)%L-shape%diameter%algorithm
双连环网(DLN)作为一种网络结构最初于1974年由D.Coppersmith和C.K.Wong提出.近年来,对DLN的研究日渐广泛.众所周知,DLN的最小距离图形(MDD)是L形的.给定一个正数N,能否找到一个双连环网,使它的直径是所有具有N个结点的DLN中最小的是一个有趣的问题.对于一个L形的图形来说,它的直径很容易计算.基于此,为了寻找到上述的DLN,许多专家进行了不懈的研究,也获得了许多好的结果.在本中,作者提出了一个寻找方形双连环网的O(1)快速算.所用方法仅涉及到初等数论的知识.
雙連環網(DLN)作為一種網絡結構最初于1974年由D.Coppersmith和C.K.Wong提齣.近年來,對DLN的研究日漸廣汎.衆所週知,DLN的最小距離圖形(MDD)是L形的.給定一箇正數N,能否找到一箇雙連環網,使它的直徑是所有具有N箇結點的DLN中最小的是一箇有趣的問題.對于一箇L形的圖形來說,它的直徑很容易計算.基于此,為瞭尋找到上述的DLN,許多專傢進行瞭不懈的研究,也穫得瞭許多好的結果.在本中,作者提齣瞭一箇尋找方形雙連環網的O(1)快速算.所用方法僅涉及到初等數論的知識.
쌍련배망(DLN)작위일충망락결구최초우1974년유D.Coppersmith화C.K.Wong제출.근년래,대DLN적연구일점엄범.음소주지,DLN적최소거리도형(MDD)시L형적.급정일개정수N,능부조도일개쌍련배망,사타적직경시소유구유N개결점적DLN중최소적시일개유취적문제.대우일개L형적도형래설,타적직경흔용역계산.기우차,위료심조도상술적DLN,허다전가진행료불해적연구,야획득료허다호적결과.재본중,작자제출료일개심조방형쌍련배망적O(1)쾌속산.소용방법부섭급도초등수론적지식.
Double Loop Network (DLN) was introduced by D. Coppersmith and C. K. Wong in 1974 and has been widely studied as architecture for local networks since then. It is well-known that the Minimum Distance Diagram (MDD) of a double loop network yields a L-shape. Given a N, it is desirable to find a double-loop network DL (N; s1, s2) with its diameter being the minimum among all double loop networks with N nodes. Since the diameter can be easily computed from a L-shape, one method is to start with a desirable L-shape and then asks whether there exist s1 and s2 (also called the steps of the DLN) to realize it. Many excellent efforts have been made to find the steps of DLNs to realize the given L-shape. In particular, the rectangular L-shape (also called the degeneration) has special characteristic as well as applications. In this paper, the author provide an excellent method to find the degeneration with an O (1) algorithm, which beats other analogues. The technique only involves some elementary number theory and is very easy to be implemented.
