Dual of a Complete Graph as an Interconnection Network

✍ Scribed by S.Q. Zheng; Jie Wu

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 284 KB
• Volume: 60
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2000.1640

✦ Synopsis

A new class of interconnection networks, the hypernetworks, has been proposed recently. Hypernetworks are characterized by hypergraphs. Compared with point-to-point networks, they allow for increased resource-sharing and communication bandwidth utilization, and they are especially suitable for optical interconnects. In this paper, we propose a scheme for deriving new hypernetworks using hypergraph duals. As an example, we investigate the dual, K n * , of the n-vertex complete graph K n and show that it has many desirable properties. We also present a set of fundamental data communication algorithms for K n * . Our results indicate that the K n * hypernetwork is a useful and promising interconnection structure for high-performance parallel and distributed computing systems.