Oriented hypercubes
Pierre Fraigniaud, Jean‐Claude König, Emmanuel Lazard · Networks · 2002
Abstract In this paper, we show how to give an orientation to the edges of an hypercube so that the inducedorientedhypercube 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 anN‐node oriented hypercube with the same communication and computational power as that of anN‐node hypercube, although with approximately the same pin‐complexity as that of a$\sqrt{N}$ ‐node hypercube. © 2002 Wiley Periodicals, Inc.