TY - GEN
T1 - Divide-and-conquer algorithms on the hypercube
AU - Mayr, Ernst W.
AU - Werchner, Ralph
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.
PY - 1993
Y1 - 1993
N2 - We show how to implement divide-and-conquer algorithms with* out 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 hypercu-bic 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 with* out 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 hypercu-bic 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=84983627203&partnerID=8YFLogxK
U2 - 10.1007/3-540-56503-5_18
DO - 10.1007/3-540-56503-5_18
M3 - Conference contribution
AN - SCOPUS:84983627203
SN - 9783540565031
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 153
EP - 162
BT - STACS 1993 - 10th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
A2 - Enjalbert, Patrice
A2 - Finkel, Alain
A2 - Wagner, Klaus W.
PB - Springer Verlag
T2 - 10th Annual Symposium on Theoretical Aspects of Computer Science, STACS 1993
Y2 - 25 February 1993 through 27 February 1993
ER -