Divide-and-Conquer Algorithms on the Hypercube
We show how to implement divide-and-conquer algorithms without undue
overhead on a wide class of networks.
We give an optimal generic divide-and-conquer implementation on
hypercubes for the class of divide-and-conquer algorithms for which
the total size of the subproblems on any level of the recursion does
not exceed the parent problem size. For this implementation,
appropriately sized subcubes have to be allocated to the subproblems
generated by the divide-steps. We take care that these allocation
steps do not cause any unbalanced distribution of work, and that,
asymptotically, they do not increase the running time. Variants of our
generic algorithm also work for the butterfly network and, by a
general simulation, for the class of hypercubic networks, including
the sh(uffle-exchange and the cube-connected-cycles network. Our
results can also be applied to optimally solve various types of
routing problems.
