Topological properties and algorithms for two‐level hypernet networks

Journal Article


Although many networks have been proposed as the topology of a large‐scale parallel and distributed system, most of them are neither expansible nor of equal degree. A network with these two properties will gain the advantages of easy implementation and low cost when it is manufactured. The hypernet, which was proposed by Hwang and Ghosh, represents a family of recursively scalable networks that are both expansible and of equal degree. In addition to the two merits, the hypernet has proven efficient for communication and computation. But, unfortunately, most topological properties and the problem of shortest‐path routing for the hypernet are still unsolved. The reason is that the structure of the hypernet is complex and asymmetric, and, especially, no mathematical description was given before. In this paper, considering current hardware restrictions, we concentrate our effort on the hypernet of moderate size. We first give a concise mathematical definition for the hypernet and then solve the following problems for the hypernet of two levels: (1) shortest‐path routing, (2) diameter, (3) connectivity, (4) minimum‐height spanning trees, and (5) embedding of rings, tori, and hypercubes. © 1998 John Wiley & Sons, Inc. Networks 31:105–118, 1998

Related Topics

Related Publications

Related Content

Site Footer


This website is provided by John Wiley & Sons Limited, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ (Company No: 00641132, VAT No: 376766987)

Published features on are checked for statistical accuracy by a panel from the European Network for Business and Industrial Statistics (ENBIS)   to whom Wiley and express their gratitude. This panel are: Ron Kenett, David Steinberg, Shirley Coleman, Irena Ograjenšek, Fabrizio Ruggeri, Rainer Göb, Philippe Castagliola, Xavier Tort-Martorell, Bart De Ketelaere, Antonio Pievatolo, Martina Vandebroek, Lance Mitchell, Gilbert Saporta, Helmut Waldl and Stelios Psarakis.