Efficient algorithms to embed Hamiltonian Paths and Cycles in faulty crossed cubes
Jianxi Fan, Wujun Zhou, Yuejuan Han, Guangquan Zhang · 2009
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 Hamiltonian path and Hamiltonian cycle. For any integer n ges 3, letting CQn(V, E) denote the n-dimensional crossed cubes and F sub V (CQn)cupE(CQn) denote a faulty set in CQn, (1) if |F| les n - 3, Hamiltonian path can construct a Hamiltonian path between any two distinct nodes in CQn- F in O(N log N) time; and (2) if |F| les n - 2, Hamiltonian cycle can construct a Hamiltonian cycle in CQn-F in O(N log N) time, where N is the node number of CQn- F.