Publications [#237092] of John H. Reif

Journal articles or Book chapters PUBLISHED

1. Miller, GL; Reif, JH, PARALLEL TREE CONTRACTION AND ITS APPLICATION., Annual Symposium on Foundations of Computer Science Proceedings (January, 1985), pp. 478-489, Portland, OR (Harvard University TR-18-85.) [pdf], [doi]
   (last updated on 2026/01/14)

   Abstract:
   The authors give a bottom-up algorithm to handle trees in which all modifications to the tree are done locally. This bottom-up approach, which they call CONTRACT, has two major advantages over the top-down approach: (1) The control structure is straightforward and easier to implement, facilitating new algorithms using fewer processors and less time. (2) Problems for which it was too difficult or too complicated to find polylog parallel algorithms are easy.