Total exchange algorithms on 'sandwich graphs' (Q1192165)

The total exchange problem in a processor network is a communication problem concerned with finding an optimal algorithm which enables every node to send a message to every other node in the network in the shortest possible time. The sandwich graph \(2G\) of a graph \(G\) is obtained by connecting all corresponding nodes in two copies of \(G\). It is shown how a good total exchange algorithm on \(G\) may be lifted to \(2G\). When applied recursively to the hypercube of dimension \(d\) this leads to an optimal total exchange algorithm taking \(2^{d-1}\) time, which is known to be the best possible.