Sequential and Parallel Subquadratic Work Algorithms for Constructing Approximately Optimal Binary Search Trees.

Marek Karpinski, Lawrence L. Larmore, Wojciech Rytter

Browse the full SODA paper archive.