Emulating direct products by index-shuffle graphs

In the theoretical framework of graph embedding and network emulations, the author shows that the index-shuffle graph (a bounded-degree hypercube-like interconnection network, introduced by Baumslag and Obrenic (1997) efficiently approximates the hypercube in general computations, by emulating the direct-product structure of the hypercube. In the direct product G=G/sub 1//spl times/G/sub 2//spl times/.../spl times/G/sub k/ let any factor G/sub i/ be an instance of any of the three following graphs: cycle, complete binary tree, X-tree. Given an N-node index-shuffle graph /spl Psi//sub n/, were N=2/sup n/, and any collection of 2/sup l/ copies of G, such that: |G/sub i/|/spl les/2(n/sub i/), for i=1,...k, where l+/spl Sigma//sub i=1//sup k/ n/sub i//spl les/n and 2([log/sub 2/ l])/spl middot/(max/sub 1/spl les/i/spl les/k/n/sub i/)/spl les/n, /spl Psi//sub n/ emulates any factor G/sub i/ in all copies of G in this collection with slowdown O(log k+log n/sub i/)=O(log log N). As a consequence of these and previous results, the index-shuffle graph emerges as a uniquely "universal" bounded-degree hypercube substitute. The index-shuffle graph emulates (multiple copies of) multi-dimensional tori and meshes of trees (or X-trees) with slowdown doubly logarithmic in the size of the graph, which currently cannot be achieved by either butterflies or shuffles. Furthermore, the butterfly is emulated by its (like-sized) index-shuffle graph with slowdown triply logarithmic in the size of the graph, which is currently impossible by shuffles. Finally, the index-shuffle graph contains the (equal-sized) shuffle-exchange graph, thus demonstrating communication power not known to be present in the hypercube itself.