Affordable Access

Publisher Website

Minimal full-access networks: Enumeration and characterization

Authors
Journal
Journal of Parallel and Distributed Computing
0743-7315
Publisher
Elsevier
Publication Date
Volume
9
Issue
4
Identifiers
DOI: 10.1016/0743-7315(90)90119-a
Disciplines
  • Computer Science

Abstract

Abstract Minimal full-access (MFA) networks are the class of all interconnection networks for 2 N = 2 n+1 inputs and outputs that require a minimum number of switching elements and provide full access capability. In this paper, MFA networks with 2 × 2 switching elements are studied. Graph-theoretic ideas used in developing previous results concerning uniform MFA networks [M. A. Sridhar and C. S. Raghavendra, J. Parallel Distrib. Comput. 5, (1988), 383–403] are generalized to show how to enumerate a large class of MFA networks. An exponential lower bound on the number of such networks is derived, and routing algorithms are outlined. In the process, a characterization of the set of automorphisms of the Omega network is derived. A characterization of the permutations realizable by a certain subclass of these networks is also derived. Finally, it is shown that a simple self-routing algorithm exists for the class of networks introduced here.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Uniform minimal full-access networks

on Journal of Parallel and Distri... Jan 01, 1988

Enumeration of minimal cuts of modified networks

on Microelectronics Reliability Jan 01, 1997

Enumeration of minimal paths of modified networks

on Microelectronics Reliability Jan 01, 1994

Exact enumeration of minimal paths of partitioned...

on Microelectronics Reliability Jan 01, 1994
More articles like this..