Technical Report CS0518

Title: UPP Graphs And UMFA Networks - Architecture for Parallel Systems
Authors: D. Goldfeld and T. Etzion
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.
CopyrightThe 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 (, 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

Computer science department, Technion