TY - GEN
T1 - Optimal tree contraction on the hypercube and related networks
AU - Mayr, Ernst W.
AU - Werchner, Ralph
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1993.
PY - 1993
Y1 - 1993
N2 - An optimal tree contraction algorithm for the boolean hypercube and the constant degree hypercubic networks, such as the shuffle exchange or the butterfly network, is presented. The algorithm is based on novel routing techniques and, for certain small subtrees, simulates optimal PRAM algorithms. For trees of size n, stored on a p processor hypercube in in-order the running time of the algorithm is O([n/p] log p). The resulting speed-up of O(p/log|p) is optimal due to logarithmic communication overhead, as shown by a corresponding lower bound.
AB - An optimal tree contraction algorithm for the boolean hypercube and the constant degree hypercubic networks, such as the shuffle exchange or the butterfly network, is presented. The algorithm is based on novel routing techniques and, for certain small subtrees, simulates optimal PRAM algorithms. For trees of size n, stored on a p processor hypercube in in-order the running time of the algorithm is O([n/p] log p). The resulting speed-up of O(p/log|p) is optimal due to logarithmic communication overhead, as shown by a corresponding lower bound.
UR - https://www.scopus.com/pages/publications/85029405775
U2 - 10.1007/3-540-57273-2_64
DO - 10.1007/3-540-57273-2_64
M3 - Conference contribution
AN - SCOPUS:85029405775
SN - 9783540572732
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 295
EP - 305
BT - Algorithms ESA 1993 – 1st Annual European Symposium, Proceedings
A2 - Lengauer, Thomas
PB - Springer Verlag
T2 - 1st Annual European Symposium on Algorithms, ESA 1993
Y2 - 30 September 1993 through 2 October 1993
ER -