連結網路的結構特性及其變形

ASIAIR > College of Computer Science > Department of Computer Science and Information Engineering > Ministry of Science and Technology Research Project > Item 310904400/9580

Please use this identifier to cite or link to this item: http://asiair.asia.edu.tw/ir/handle/310904400/9580

Title:	連結網路的結構特性及其變形
Authors:	龔自良
Contributors:	健康學院資訊工程學系
Keywords:	連結網路圖形泛連通漢彌爾頓迴圏路徑 Interconnection network Graph Panconnected Hamiltonian Cycle Path
Date:	2009
Issue Date:	2010-05-12 05:28:03 (UTC+0)
Abstract:	將數以百計的計算元件有系統地組織成電腦模組有助於解決許多真實世界中所面臨的計算問題，從而使得連結網路（interconnection network）成為影響系統效能的關鍵因素。由於結構嵌入（embedding）實現了不同系統之間低變動成本的模組可攜性，因此嵌入方法的開發成為一個重要的研究議題。在平行與分散式計算中，線性陣列與環是二種最常被使用到的結構，因此本計畫將以探索高效率的路徑與迴圈嵌入方法為主要目標（目標一），並討論二個與路徑嵌入相關的網路結構性質及其變形（目標二及目標三）。這兩個特性分別為泛連通性（panconnectedness）及漢彌爾頓性質（Hamiltonicity）。目標一：連結網路上高效率的迴圈與路嵌入在連結網路上嵌入特定長度的迴圈或路徑分別對應到泛圈性（pancyclicity）或泛連通性（panconnectedness）二種結構性質。所謂泛圈性，是指一個網路G 具有長度從3 到\|V(G)\| 之間任一長度的迴圈，符號V(G)表示網路G 的點集合；所謂泛連通性，是指一個網路G 在任意兩個節點x 與y 之間具有長度從dG(x,y)到\|V(G)\|之間任一長度的路徑，其中符號dG(x,y) 表示節點x 與y 之間的距離。由於網路元件可能隨時因偶發性的損壞而失去正常功能，所以在實務上非常需要將網路容錯相關的議題納入考量。因此本計畫將特別就容錯式泛連通性質進行研究。目標二：泛連通性及其變形本研究將提出兩種泛連通性的變形，並加以深入討論。第一種變形被稱為泛置泛連通性（ panpositionable panconnectedness ），第二種變形稱之為雙分路徑泛連通性（two-disjoint-path panconnectedness）。由這兩種性質可以分別推導出其他與路徑嵌入相關的網路特性。目標三：漢彌爾頓性質及其變形在任何給定的圖形中尋找漢彌爾迴圈為著名的 NP 完備（NP-complete）問題，也因此被許多研究人員所深入地討論過。本計畫將針對一種漢彌爾頓性質的變形進行研究，此變形在文獻中被稱為相互獨立漢彌爾頓迴圈（mutually independent Hamiltonian cycles），與給定的圖形中所具有的漢彌爾頓迴圈的數量有關。我們將針對幾個著名的連結網路結構來探討這個性質。 The attempt to interconnect hundreds or more processing elements in computers is of use to solve numerous real-world problems, so that the interconnection network is mostly a critical factor affecting the system performance. In particular, network embedding is of great importance because the portability between the guest and host networks would permit executing the guest specified algorithms on the host with as little modification as possible. Since linear arrays and rings are two of the most fundamental structures for parallel and distributed computation, this project is aimed to explore the efficient methods of cycle and path embedding (Aim 1), and to address two topological properties and their variations related to path embedding in interconnection networks: one is panconnectedness (Aim 2) and the other is Hamiltonicity (Aim 3). Aim 1: Efficient Cycle and Path Embedding in Interconnection networks The problem of embedding cycles or paths of the given length into interconnection networks corresponds to the concept of pancyclicity or panconnectedness, respectively. A network G is called pancyclic if it contains a cycle of length l for each integer l from 3 to \|V(G)\| inclusive, where V(G) denotes the vertex set of G. A network G is said to be panconnected if, for any two distinct vertices x and y, it has an [x,y]-path of length l for each dG(x,y)≤l≤\|V(G)\|-1, where dG(x,y) denotes the distance between x and y in G. In practice, because the network components may have no function accidentally, it is greatly demanded to take the fault-tolerance related issues into account. In this proposal the fault-tolerant panconnectedness will be addressed. Aim 2: On the Variations of Panconnectedness As our extension of the original panconnectedness property, two possible variations are considered in this study. One is called panpositionable panconnectedness (Aim 2.1), and the other is called two-disjoint-path panconnectedness (Aim 2.2). Then many other topological properties of interconnection networks follow immediately. Aim 3: On the Variation of Hamiltonicity The problem of finding a Hamiltonian cycle in a graph is well known to be NP-complete, and thus has been widely discussed. In this proposal we address the concept of mutually independent Hamiltonian cycles, which is related to the number of Hamiltonian cycles in a given graph. In particular, this concept will be concerned with respect to some classes of interconnection networks.
Appears in Collections:	[Department of Computer Science and Information Engineering] Ministry of Science and Technology Research Project

Files in This Item:

File	Size	Format
98龔自良1.pdf	80Kb	Adobe PDF	286	View/Open
98龔自良2.pdf	71Kb	Adobe PDF	296	View/Open
index.html	0Kb	HTML	418	View/Open

Loading...