[Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol. 16, No. 2, pp. 291-300 (March 2000)

Incrementally Extensible Folded Hypercube Graphs

Hung-Yi Chang and Rong-Jay Chen
Department of Information Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

In this paper, we propose the incrementally extensible folded hypercube (IEFH) graph as a new class of interconnection networks for an arbitrary number of nodes. We show that this system is optimal fault tolerant and almost regular (i.e., the difference between the maximum and the minimum degree of nodes is at most one). The diameter of this topology is half of that of the incomplete hypercube (IH), the supercube, or the IEH graph. We also devise a simple routing algorithm for the IEFH graph. Finally, we embed cycles and complete binary trees into this graph optimally.

Keywords: hypercubes, folded hypercubes, incrementally extensible hypercubes, fault tolerance, graph embeeding, interconnection networks

Full Text () Retrieve PDF document (200003_07.pdf : 3,563,874 bytes)

Received January 13, 1999; revised August 20, 1999; accepted November 26, 1999.
Communicated by Shang-Rong Tsai.