Off-campus South Dakota State University users: To download campus access theses, please use the following link to log into our proxy server with your South Dakota State University ID and password.

Non-South Dakota State University users: Please talk to your librarian about requesting this thesis through interlibrary loan.

Author

Sanjay Sharma

Document Type

Thesis - University Access Only

Award Date

1993

Degree Name

Master of Science (MS)

Department

Electrical Engineering

First Advisor

Bin Cong

Abstract

Simulation of one interconnection topology by another has several applications in efficient uses of parallel computation networks. The Fibonacci Cube network was proposed recently, [16], [17], (18], [19], [20], [21] as an alternative to the Hypercube networks. Fibonacci Cube networks have rich properties of Fibonacci numbers and hence they can flexibly be decomposed into subgraphs of the same kind. However, there is a tremendous gap between Hypercubes and Fibonacci Cubes with respect to the availability of routing and graph embedding results. These problems have been studied extensively on Hypercubes [2], [4], [6], [7], [24], [25], [27], [28]. In this paper we investigate embeddings of Binary Tree, X-Tree, Arbitrary Binary Tree, Linear Arrays, 2-D Mesh and Ring interconnection networks. The embeddings discussed show that Fibonacci Cube network can efficiently simulate them. They are, in fact, optimum or nearly optimum in both dilation and expansion.

Library of Congress Subject Headings

Electric network topology
Computer networks
Fibonacci numbers

Format

application/pdf

Publisher

South Dakota State University

Share

COinS