标题: ㄧ个只花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
作者: 唐文祥
Wen-shiang Tang
陈秋媛
Dr. Chiuyuan Chen
应用数学系所
关键字: 双环式网路;L-型;直径;演算法;三环式网路;hyper-L型;Double-loop network;L-shape;diameter;algorithm;triple-loop network;hyper-L tile
公开日期: 2003
摘要: 双环式网路及三环式网路是许多学者专家广泛探讨的区域网路架构。给定一个正整数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
显示于类别:Thesis


文件中的档案:

  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.