標題: 雙環連結網路的最小直徑
Double-Loop Networks with Minimum Diameter
作者: 王治平
Chih-Ping Wang
陳秋媛
Chiuyuan Chen
應用數學系所
關鍵字: 直徑;雙環連結網路;L-shape;diameter;double-loop networks;L-型
公開日期: 1999
摘要: 雙環聯結網路是一種廣泛被研究的區域網路架構。N表示網路中節點的個數,d(N) 表示在一N個節點的雙環網路中有可能最短的直徑。Wong and Coppersmith 證明了$d(N) \ge \left\lceil \sqrt{3N}\right\rceil -2$ □ 。這是一個廣為大家所知d(N)的下界,表示作lb(N)。給定N,如果可找出一個雙環連結網路的直徑剛好等於lb(N),那就可以清楚的知道這有N個節點的雙環聯結網路的直徑是最小的。之前有許多人用此方法找出了一些可達到最小直徑的不同型態的N,但是在d(N) > lb(N)的情形下,只有少數的結果被知道。在這篇論文中,我們找出了兩種型態有d(N) = lb(N) + 1性質的N。
Double-loop networks have been widely studied as an architecture for local area networks. Let N denote the number of stations in a double-loop network and let d(N) be the best possible diameter of a double-loop network with N vertices. Wong and Coppersmith showed that $d(N) \ge \left\lceil \sqrt{3N}\right\rceil -2$. This is a well-known lower bound for d(N) and is usually denoted as lb(N). Given an N, if one can find a double-loop network with its diameter being equal to lb(N), then clearly this network is a minimum diameter double-loop network with N stations; this is the way that many authors found minimum diameter double-loop networks for some classes of values of N. When d(N) > lb(N), only a few results about minimum diameter double-loop networks are known. In this paper, we find minimum diameter double-loop networks for two classes of values of N when d(N) = lb(N) + 1.
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT880507022
http://hdl.handle.net/11536/66173
Appears in Collections:Thesis