Title: ㄧ個只花O(log N)時間找出具有N點之雙環式網路的steps的演算法以及Hyper-L1三環式網路的存在性的探討
An O(log N)-Time Algorithm to Find the Steps of a Double-Loop Network with N Nodes and the Existence of Hyper-L1 Triple-Loop Networks
Authors: 唐文祥
Wen-shiang Tang
陳秋媛
Dr. Chiuyuan Chen
應用數學系所
Keywords: 雙環式網路;L-型;直徑;演算法;三環式網路;hyper-L型;Double-loop network;L-shape;diameter;algorithm;triple-loop network;hyper-L tile
Issue Date: 2003
Abstract: 雙環式網路及三環式網路是許多學者專家廣泛探討的區域網路架構。給定一個正整數N,找出具有N點、直徑最小的雙環式網路DL(N;s1,s2)的s1和s2(又稱為steps)是學者專家們ㄧ直以來所想達成的目標。已知雙環式網路的minimum distance diagram是L-型;對於雙環式網路而言,直徑可以很容易的由它的L-型計算出。因此「找出具有N點、直徑最小的雙環式網路」的一個常見的方法是:將此問題轉換為「先找出一個直徑相當不錯的L-型,再找出與這個L-型對應的雙環式網路DL(N; s1, s2)的s1和s2」。給定一個雙環式網路DL(N; s1, s2),在論文[8]中,Cheng和黃光明老師提出了一個漂亮而且只花O(log N)時間、找出對應的L-型的演算法。但是,「給定一個L-型,是否能夠只花O(log N)時間,找出與這個L-型相對應的雙環式網路DL(N; s1, s2)的steps」,卻一直是一個open problem [5]。在這篇論文裡,我們提出一個只花O(log N)時間、找出與一個給定的L-型相對應的雙環式網路DL(N; s1, s2)的steps的演算法。
令N(D)表示一個直徑為D的三環式網路所能包含的最多點數。Hyper-L型已被多位學者發現為推導出N(D)的下界的一個有效的工具。然而,並非每一個Hyper-L 型都會有一個三環式網路來得到它。截至目前為止,共有三種hyper-L型被學者們提出來,為了方便起見,我們分別稱它們為hyper-L0、hyper-L1、hyper-L2。在論文[7]中,陳秋媛老師、黃光明老師、李珠矽老師、以及石舜仁學長提出了hyper-L0三環式網路存在的充份必要條件。在這篇論文裡,我們提出hyper-L1三環式網路存在的充份必要條件。
Double-loop networks and triple-loop networks have been widely studied as architecture for local area networks. Given an 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. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Since the diameter can be easily computed from an 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 double-loop network) to realize it. While Cheng and Hwang [8] have given an elegant O(log N)-time algorithm to find the L-shape of a double-loop network DL(N; s1, s2), it is an open problem whether the steps of a double-loop network with N nodes can be found in O(log N) time [5]. In this thesis, we propose an O(log N)-time algorithm to find the steps of a double-loop network with N nodes.
Hyper-L tiles were proven to be an effective tool to obtain lower bounds for N(D), the maximum number of nodes in a triple-loop network with diameter D. Unfortunately, not every hyper-L tile has a triple-loop network realizing it. Up to now, three types of hyper-L tiles have been proposed; for convenience, call them hyper-L0, hyper-L1, and hyper-L2. In [7], Chen et al. derived the necessary and sufficient conditions for the existence of hyper-L0 triple-loop networks. In this thesis, we shall derive the necessary and sufficient conditions for the existence of hyper-L1 triple-loop networks.
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT009122533
http://hdl.handle.net/11536/52458
Appears in Collections:Thesis


Files in This Item:

  1. 253301.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.