| TR#: | CS0518 |
| Class: | CS |
| Title: | UPP Graphs And UMFA Networks - Architecture for Parallel Systems |
| Authors: | D. Goldfeld and T. Etzion |
| CS0518.pdf | |
| Abstract: | A graph with unique path property (UPP) has 2^n vertices and a unique path of length n between each two vertices. These graphs are very important in the design of architectures and algorithms for interconnection networks. Given two UPP graphs we introduce an algorithm to determine isomorphism between the graphs. We give two different constructions for nonisomorphic UPP graphs and show a lower bound of 2^((2^(n+1)-3n-2)/9) nonisomorphic graphs with 2^n vertices. UMFA (Uniform Minimal Full Access) networks are multistage interconnection networks, that use the same interconnection pattern between each two consecutive stages. These networks are derived from UPP graphs, and the most known network of this type is the Omega network. We deal with the problem of rearrangeability of UMFA networks. |
| Copyright | The above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information |
Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1988/CS/CS0518), rather than to the URL of the PDF files directly. The latter URLs may change without notice.
To the list of the CS technical reports of 1988
To the main CS technical reports page