Efficient Algorithms to Embed Hamiltonian Paths and Cycles in Faulty Crossed Cubes

摘要：

The crossed cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. Hamiltonicity is a critical property in interconnection networks. In this paper, we study fault-tolerant embedding algorithms of Hamiltonian paths and cycles in crossed cubes. We provide two algorithms HamiltonianPath and HamiltonianCycle. For any integer n ≥ 3, letting CQn(V,E) denote the n-dimensional crossed cubes and F (∩) V (CQn) ∪ E(CQn) denote a faulty set in CQn, (1) if |F| ≤ n-3, HamiltonianPath can construct a Hamiltonian path between any two distinct nodes in CQn -F in O(NlogN) time; and (2) if |F| ≤ n-2, Hamiltoniancycle can construct a Hamiltonian cycle in CQn-F in O(NlongN)time, where N is the node number of CQn-F.

关键词： Crossed cube fault-tolerant path embedding dilation parallel computing system

作者: Jianxi Fan Wujun Zhou Yuejuan Han Guangquan Zhang

作者单位: School of Computer Science and Technology Soochow University Suzhou 215006, China

会议类型: 国际会议

会议名称: 第四届国际计算机新科技与教育学术会议(2009 4th International Conference on Computer Science & Education)

会议地点: 南京

会议语种:英文

页码: 1837-1842

在线出版日期: 2009-07-25（万方平台首次上网日期，不代表论文的发表时间）