混合的弦環式網路之直徑

Abstract

在文獻 [3]中, 陳尚寬學長, 黃光明老師, 以及劉昱綺學姊提出了「混合的弦環式網路」的一個新的網路架構。 他們推導出「混合的弦環式網路」的直徑的上下界, 發現「混合的弦環式網路」的直徑可達到(2N)^(1/2) (N為網路中的節點數), 相較於使用相同數量硬體的雙環式網路而言, 這是一項很大的改進。 在這篇論文中, 我們提出一個只花O(logN)時間的計算「混合的弦環式網路」的直徑的演算法。

Recently, Chen, Hwang and Liu [3] proposed a new network called the mixed chordal ring network which is very comparable to the double-loop network. They proved the surprising result that the mixed chordal ring network can achieve diameter about (2N)^(1/2) which is a huge improvement over the double-loop network (here N is the number of nodes in the network). They derived the upper and the lower bounds for the diameter of a mixed chordal ring network. The purpose of this thesis is to propose an O(log N)-time algorithm for deriving the exact value of the diameter of a mixed chordal ring network.