Date: Tue, 10 Dec 1996 21:21:42 GMT
Server: NCSA/1.4.2
Content-type: text/html
Last-modified: Mon, 04 Sep 1995 19:47:16 GMT
Content-length: 3084
Upper and Lower Bounds on Constructing Alphabetic Binary Trees
Next: Overview
Upper and Lower Bounds on Constructing Alphabetic Binary Trees
MARIA KLAWE
and
BRENDAN MUMEY
Abstract:
This paper studies the long-standing open question of whether
optimal alphabetic binary trees can be constructed in
time. We show that a class of techniques for
finding optimal alphabetic trees which includes all current
methods yielding
time algorithms are at least
as hard as sorting in whatever model of computation is used.
We also give
time algorithms for the case where all the input
weights are within a constant factor of one another and when
they are exponentially separated.
Brendan Mumey
Mon Sep 4 11:52:47 PDT 1995