嵌入兩條邊互斥的漢彌爾頓迴路在可分解網路上

Embedding Two Edge-Disjoint Hamiltonian Cycles in Decomposable Networks

廖建智(Chien-Chih Liao)

指導教授 ： 洪若偉

朝陽科技大學/資訊學院/資訊工程系/碩士(2013年)

摘要

當在執行演算法需要用到環型結構讓訊息可以用平行方式在網路中傳播，邊互斥漢彌爾頓迴路的存在提供了這一個優勢。邊互斥的漢彌爾頓迴路在互聯網路中還提供了邊容錯的漢彌爾頓性。在本論文中，將提出一個在互聯網路中新的類別，稱為可分解網路。在立方體，跟立方體的多數變形和換位網路都屬於可分解網路的類別。在可分解網路類別中超立方體是最為重要的變形。本論文將提出統一的遞迴方法，去建構兩條邊互斥的漢彌爾頓迴路在我們介紹的網路。使用我們所提出的遞迴方法，我們設計線性時間演算法來建構一些可分解網路兩條互斥的漢彌爾頓迴路，其中包括雙扭立方體、換位網路、增廣立方體跟交叉立方體。

關鍵字

扭曲立方體 ； 換位網路 ； 增廣立方體 ； 交叉立方體 ； 可分解互聯網路 ； 邊不相交的漢彌爾頓迴路

並列摘要

The presence of edge-disjoint Hamiltonian cycles provides an advantage when implementing algorithms that require a ring structure by allowing message traffic to be spread evenly across the network. Edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity of an interconnection network. In this thesis, we first introduce a new class of interconnection networks, called decomposable networks. The hypercubes, the most variations of hypercubes, and the transposition networks are in the class of decomposable networks. We then propose a unified recursive method to construct two edge-disjoint Hamiltonian cycles in the introduced class of networks. Using the proposed recursive method, we present linear time algorithms to construct two edge-disjoint Hamiltonian cycles on some decomposable networks, including twisted cubes, transposition networks, augmented cubes, and crossed cubes.

並列關鍵字

augmented cubes ； transposition networks ； twisted cubes ； edge-disjoint Hamiltonian cycles ； decomposable interconnection networks ； crossed cubes

參考文獻

[1] S. Abraham and K. Padmanabhan, “The twisted cube topology for multiprocessors: a study in network asymmetry,” J. Parallel Distrib. Comput., vol. 13, pp. 104–110, 1991.

[2] A.B. Akers and B. Krishnamurthy, “A group-theoretic model for symmetric interconnection networks,” IEEE Trans. Comput., vol. 38, pp. 555–565, 1989.

[3] M.M. Bae and B. Bose, “Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes,” IEEE Trans. Comput., vol. 52, pp. 1271–1284, 2003.

[4] D. Barth and A. Raspaud, “Two edge-disjoint Hamiltonian cycles in the butterfly graph,” Inform. Process. Lett., vol. 51, pp. 175–179, 1994.

[5] L.N. Bhuyan and D.P. Agrawal, “Generalized hypercube and hyperbus structures for a computer network,” IEEE Trans. Comput., vol. C-33, pp. 323–333, 1984.