在局部扭曲立方體中建構兩個不相交的漢密頓圈之平行演算法設計

A Parallel Algorithm for Constructing Two Edge-disjoint Hamiltonian Cycles in Locally Twisted Cubes

李順玉(Shun-Yu Li)

指導教授 ： 張肇明

國立臺北商業大學/管理學院/資訊與決策科學研究所/碩士(2021年)

摘要

局部扭曲立方體LTQn是超立方體Qn的一種變形，並且直徑只有超立方體的一半，在交換網路中，以環形結構為基礎可以設計出一些有效的通訊演算法。另外，兩個邊不相交的漢密頓圈也為交換網路提供了邊容錯的漢密頓 性。Hung在2011年設計了一種花費O(n2n)時間複雜度的演算法，在LTQn中建構出兩個邊不相交的漢密頓圈。本篇論文中，我們為LTQn中的每一個點提供一種平行演算法，以確定在第一個或是第二個漢密頓圈中分別採用了哪兩條邊，通過連接這些邊，我們可以在n ≥ 4的LTQn中建構出兩個邊不相交的漢密頓圈。

關鍵字

邊不相交的漢密頓圈 ； 局部扭曲立方體 ； 交換網路

並列摘要

The locally twisted cube LTQn is a variation of the hypercube Qn, and the diameter of LTQn is only about half of the diameter of Qn. For interconnection, some efficient communication algorithms can be designed based on the ring structure. In addition, two edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity for the interconnection network. Hung [Theoretical Computer Science 412, 4747–4753, 2011] designed an O(n2n) time algorithm to construct two edge-disjoint Hamiltonian cycles in LTQn. In this thesis, we provide parallel algorithms for each vertex in LTQn to determine which two edges were adopted in the first or second Hamiltonian cycles, respectively. By connecting these edges, we can construct two edge-disjoint Hamiltonian cycles in LTQn where n ≥ 4.

並列關鍵字

edge-disjoint Hamiltonian cycles ； locally twisted cubes ； interconnection networks

參考文獻

[1] Bae, M. M. and Bose, B. (2003). Edge disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes. IEEE Transactions on Computers, 52(10), 1271-1284.

[2] Barth, D. and Raspaud, A. (1994). Two edge-disjoint Hamiltonian cycles in the butterfly graph. Information Processing Letters, 51, 175-179.

[3] Han, Y., Fan, J., Yang, J., and Qian, P. (2009). Path embedding in faulty locally twisted cubes. In: 2nd IEEE International Conference on Computer Science and Information Technology (2009), August 8-11, Beijing, China, 214- 218, IEEE.

[4] Hsieh, S. Y. and Wu, C. Y. (2010). Edge-fault-tolerant hamiltonicity of locally twisted cubes under conditional edge faults. Journal of Combinatorial Optimization, 19(1), 16-30.

[5] Hu, K. S., Yeoh, S. S., Chen, C., and Hsu, L. H. (2007). Node-pancyclicity and edge-pancyclicity of hypercube variants. Information Processing Letters, 102(1), 1-7.