DocumentCode :
3231082
Title :
Efficient algorithms to embed Hamiltonian Paths and Cycles in faulty crossed cubes
Author :
Fan, Jianxi ; Zhou, Wujun ; Han, Yuejuan ; Zhang, Guangquan
Author_Institution :
Sch. of Comput. Sci. & Technol., Soochow Univ., Suzhou, China
fYear :
2009
fDate :
25-28 July 2009
Firstpage :
1837
Lastpage :
1842
Abstract :
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.
Keywords :
graph theory; hypercube networks; Hamiltonian path; fault-tolerant embedding algorithm; faulty crossed cube; graph theory; hypercube network; interconnection network; node number; Computational modeling; Computer architecture; Computer science; Computer science education; Educational technology; Fault tolerance; Hypercubes; Multicast algorithms; Multiprocessor interconnection networks; Parallel processing; Crossed cube; dilation; embedding; fault-tolerant; parallel computing system; path;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science & Education, 2009. ICCSE '09. 4th International Conference on
Conference_Location :
Nanning
Print_ISBN :
978-1-4244-3520-3
Electronic_ISBN :
978-1-4244-3521-0
Type :
conf
DOI :
10.1109/ICCSE.2009.5228259
Filename :
5228259
Link To Document :
بازگشت