連結網路上多重資料傳輸及偶泛連通性之研究

On the mutually independent property and bipanconnected property of some interconnection networks

石圜鋼(Yuan-Kang Shih)

指導教授 ： 譚建民 ； 徐力行

國立交通大學/資訊學院/資訊科學與工程研究所/博士(2012年)

https://doi.org/10.6842/NCTU.2012.00076

摘要

從應用的觀點來看，演算法效率及執行模式是對於網路上訊息溝通的重要議題之一。為了提供理想效能的系統性和邏輯性分析，於是我們就去研究網路設計上拓樸結構。此外，由另一個網路去模擬某一個網路的問題就是所謂的嵌入問題，而在連結網路上，迴圈嵌入問題就是最熱門的研究之一。
在這篇博士論文中，我們將會介紹偶泛圈性、偶泛定位性以及偶泛定位偶泛圈性，並且會證明某些連結網路拓樸將會滿足這些性質。我們也將會研究在連結網路上，是否有存在著相互獨立迴圈。在網路通訊系統中，相互獨立迴圈可以保證在平行傳輸時，不會同時有若干待處理的資訊集中在特定的處理器上，因此可以保證在平行傳輸時，沒有等待的時間。而我們提出了一個充分條件來保證在某種特定條件下的連結網路，存在特定數量的相互獨立迴圈，並且我們也證明出在某些特定連結網路上，相互獨立漢米爾頓迴圈的最佳化數量。在這篇論文的最後，我們將會介紹兩個新的概念，稱之為相互獨立邊-偶泛圈性以及相互獨立偶泛連通性。我們所提出的新概念將會加強之前所得到的結果，包括了偶泛圈性、偶泛連通性、邊-偶泛圈性以及點-偶泛圈性。

關鍵字

連結網路 ； 泛圈性 ； 泛連通性 ； 泛定位性 ； 相互獨立

並列摘要

From the application point of view, efficient algorithms and execution methods are important issues for communication patterns in networks. The study of certain topological structures on network designs provides a systematic and logical analysis for the desired performance. The problem of simulating a network by another is called embedding problem. The cycle-embedding problem is one of the most popular research problems.
In this dissertation, we will introduce the bipancyclic property, bipanpositionable property, and bipanpositionable bipancyclic property, and show that some interconnection networks satisfy those properties. We also study the existence of mutually independent cycles on some interconnection networks. The existence of mutually independent cycles in communication system guarantees that there will be no waiting time for parallel processing. We propose a sufficient condition to guarantee the existence of certain number of mutually independent hamiltonian cycles. We also find the optimal number of mutually independent hamiltonian cycles in some special interconnection networks. Finally, we will introduce two new concepts called mutually independent edge-bipancyclic property and mutually independent bipanconnected property. Our result strengthens previous results such as bipancyclic property, bipanconnected property, edge-bipancyclic property, and vertex-bipancyclic property.

並列關鍵字

interconnection networks ； pancyclic property ； panconnected property ； panpositionable property ； mutually independent

參考文獻

[2] B. Alspach and D. Hare, “Edge-pancyclic Block-intersection Graphs,” Discrete Mathematics,Vol. 97, pp. 17–24, 1997.

[3] T. Araki, “Edge-Pancyclicity of Recursive Circulants,” Information Processing Letters, Vol. 88, pp. 287–292, 2003.

[4] T. Araki, “Hyper Hamiltonian Laceability of Cayley Graphs Generated by Transpositions,” Networks, Vol 48, pp. 121–124, 2006.

[6] R. Caha and V. Koubek, “Spanning Multi-Paths in Hypercubes,” Discrete Mathematics, Vol. 307, pp. 2053–2066, 2007.

[7] C.-H. Chang, C.-K. Lin, H.-M. Huang, and L.-H. Hsu, “The Super Laceability of the Hypercubes,” Information Processing Letters, Vol. 92, pp. 15–21, 2004.