neal young / Chrobak21Simple

  • under review:11 pages(2021)
    publication/Chrobak21Simple.png In 1971, Knuth gave an O(n2)-time algorithm for the classic problem of finding an optimal binary search tree. Knuth's algorithm works only for search trees based on 3-way comparisons, while most modern computers support only 2-way comparisons (e.g., <, <=, =, >=, and >). Until this paper, the problem of finding an optimal search tree using 2-way comparisons remained open --- poly-time algorithms were known only for restricted variants. We give an O(n4)-time algorithm for the general case. The algorithm and analysis are simpler than those for the previously solved special case.

© Copyrights are reserved by the publishers.
Download for personal and limited academic use only.