HIERARCHIC GRAPHS BASED ON THE FIBONACCI NUMBERS

Year 2007, Volume: 7 Issue: 1, 345 - 365, 02.01.2012

Ali Karcı

Abstract

   

Keywords

-

References

• Sagan, “The Twisted n-cube with application to multiprocessing”, IEEE Transactions on Computers, vol.40, pp.88-93, 1991.
• • The number of edges in HFC(n) ⎡ isf⎢⎣ n and lower diameter”, IEEE Transactions on Computers, vol. 40, pp. 1312-1316, 1991. the number of edges in HEFCk(n) is
• K. Efe, “A variation on the hypercube with A. S. Vaidya, P. S. N. Rao, and S. R. Shankar, “A class of hypercube-like networks”, Tech. Rep. EE/01/93, Dept. of Electrical Eng., Indian Institute of Science, Bangalore, 1993. k( fn n).[E(k+) k().[E(k+) ef().[E(k+) −k3−3 nk3−3 ∑3ief( i= ⎦⎥ −3+
• • HFC(n)s have node degrees between ⎥⎥ Cubic Networks”, IEEE Transactions on Parallel and Distributed Systems, vol. 6, pp.427-435, n⎤1 ⎢⎢ ⎡ HEFCk(n) is between ⎢⎢ )and (k +k )1⎤ ⎥⎥ (k n-1. W.-J. Hsu, “Fibonacci Cubes – A New Interconnection Topology”, IEEE Transactions on Parallel and Distributed Systems, vol. 4, pp. 12, 1993.
• • All HFC(n), HEFC1(n), …, HEFCk(n) can be decomposed to lower sized HFC(r), HEFC1(r), …, HEFCk(r), r<n. Thus, HFC(n), HEFC(n), …, HEFCk(n) have self-similarity property. These graphs have recurrent structures which are essential in developing fault-tolerant Networking (ICOIN-15), Jan. 31 - Feb. 2, 2001, schemes.
• Beppu Convention(B-Con) Plaza, Beppu City, Japan. • Due to HFC(n), HEFC1(n), …, HEFCk(n) having recurrent structures, recursive-descent and recursive-doubling algorithms can be [7] A. Karci, “Recursive Construction of developed on HFC(n), HEFC1(n), …, Hierarchical Fibonacci Cubes and Hierarchical HEFCk(n) easily, if these graphs are used as interconnection networks. Extended Fibonacci Cubes”, IEEE: 2001
• International Conference on Parallel and Distributed Systems (ICPADS-2001), June 26
• • If path P in one of HFC(n), HEFC HEFCk(n) contains three or more diagonal 29, 2001, KyongJu city, Korea. links, then P is not a shortest path.
• J. Duato, S. Yalamanchili, and L. Ni, “Interconnection networks – An engineering approach”, IEEE Computer Society Press, 1997. diagonal links. Appendix edges (a) f h (b)