A general class of resource tradeoffs

摘要

In this paper, we study a class of resource tradeoffs that arise in such problems as parallel sorting algorithms, linear recursion schemata, VLSI layouts, and searching algorithms. The tradeoffs can all be traced to the common structure of a multiway tree, and the special class of binomial trees (which are structurally related to the binomial coefficients) correspond to particularly efficient algorithms. Although most of the tradeoff's that we exhibit are upper bounds, we present several examples to show that the approach can also lead to lower bounds.