Premium
Oriented hypercubes
Author(s) -
Fraigniaud Pierre,
König JeanClaude,
Lazard Emmanuel
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10012
Subject(s) - hypercube , node (physics) , computer science , power of two , routing (electronic design automation) , construct (python library) , combinatorics , broadcasting (networking) , parallel computing , discrete mathematics , mathematics , algorithm , computer network , physics , quantum mechanics
Abstract In this paper, we show how to give an orientation to the edges of an hypercube so that the induced oriented hypercube offers approximately the same communication performance as that of the original nonoriented hypercube (routing, broadcasting, connectivity, etc.), that is, we show that it is possible to construct an N ‐node oriented hypercube with the same communication and computational power as that of an N ‐node hypercube, although with approximately the same pin‐complexity as that of a $\sqrt{N}$ ‐node hypercube. © 2002 Wiley Periodicals, Inc.