Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Applied Mathematics
Alphabetic Minimax Trees Of Degree At Most T*, D. Coppersmith, Maria M. Klawe, Nicholas Pippenger
Alphabetic Minimax Trees Of Degree At Most T*, D. Coppersmith, Maria M. Klawe, Nicholas Pippenger
All HMC Faculty Publications and Research
Problems in circuit fan-out reduction motivate the study of constructing various types of weighted trees that are optimal with respect to maximum weighted path length. An upper bound on the maximum weighted path length and an efficient construction algorithm will be presented for trees of degree at most t, along with their implications for circuit fan-out reduction.
Superconcentrators, Nicholas Pippenger
Superconcentrators, Nicholas Pippenger
All HMC Faculty Publications and Research
An $n$-superconcentrator is an acyclic directed graph with $n$ inputs and $n$ outputs for which, for every $r \leqq n$, every set of $r$ inputs, and every set of $r$ outputs, there exists an $r$-flow (a set of $r$ vertex-disjoint directed paths) from the given inputs to the given outputs. We show that there exist $n$-superconcentrators with $39n + O(\log n)$ (in fact, at most $40n$) edges, depth $O(\log n)$, and maximum degree (in-degree plus out-degree) 16.