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.