Title :
Hamiltonian Connectedness of Recursive Dual-Net
Author :
Li, Yamin ; Peng, Shietung ; Chu, Wanming
Author_Institution :
Dept. of Comput. Sci., Hosei Univ., Koganei, Japan
Abstract :
Recursive Dual-Net (RDN) was proposed recently as an effective, high-performance interconnection network for supercomputers with millions of nodes. A Recursive Dual-Net RDN (B) is recursively constructed on a base symmetric network B. At each iteration, the network is extended through dual-construction. The dual-construction extends a symmetric graph G into a symmetric graph G´ with size 2n2 and node-degree d + 1, where n and d are the size and the node-degree of G, respectively. Therefore, a k-level Recursive Dual-Net RDNk (B) contains (2n0)2k/2 nodes with a node degree of d0 + k, where n0 and d0 are the size and the node-degree of the base network B, respectively. In this paper, we show that, if the base network B is hamiltonian, RDNk (B) is hamiltonian. We give an efficient algorithm for constructing a hamiltonian cycle in RDNk (B) for k > 0. We also show that if the base network is hamiltonian connected, RDNk (B) is hamiltonian connected for any k > 0.
Keywords :
graph theory; multiprocessor interconnection networks; parallel machines; Hamiltonian connectedness; recursive dual-net; supercomputers interconnection network; symmetric graph; Computational complexity; Computational efficiency; Computer networks; Computer science; Hardware; Hypercubes; Information technology; Large-scale systems; Multiprocessor interconnection networks; Supercomputers; hamiltonian; hamiltonian connected; interconnection network; supercomputers;
Conference_Titel :
Computer and Information Technology, 2009. CIT '09. Ninth IEEE International Conference on
Conference_Location :
Xiamen
Print_ISBN :
978-0-7695-3836-5
DOI :
10.1109/CIT.2009.17