TY - JOUR
T1 - Divide-and-conquer algorithms on the hypercube
AU - Mayr, Ernst W.
AU - Werchner, Ralph
PY - 1996/8/20
Y1 - 1996/8/20
N2 - 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 shuffle-exchange and the cube-connected-cycles network. Our results can also be applied to optimally solve various types of routing problems.
AB - 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 shuffle-exchange and the cube-connected-cycles network. Our results can also be applied to optimally solve various types of routing problems.
UR - http://www.scopus.com/inward/record.url?scp=0030214596&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(96)00033-3
DO - 10.1016/0304-3975(96)00033-3
M3 - Article
AN - SCOPUS:0030214596
SN - 0304-3975
VL - 162
SP - 283
EP - 296
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -