| 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. |
