A New Algorithm for Minimum Cost Binary Trees

DOI10.1137/0206045zbMath0366.68028OpenAlexW1988325634MaRDI QIDQ4142686

Michelle L. Wachs, Adriano M. Garsia

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206045

Mathematics Subject Classification ID

Trees (05C05) Algorithms in computer science (68W99)

Related Items (18)

Set Orderings Requiring Costliest Alphabetic Binary Trees ⋮ Average complexity of searching for identical objects in random nonuniform databases ⋮ On the redundancy of \(D\)-ary Fano codes ⋮ Efficient Construction of Near-Optimal Binary and Multiway Search Trees ⋮ Operations research applications of dichotomous search ⋮ Correctness of constructing optimal alphabetic trees revisited ⋮ Optimum multiway search trees ⋮ An optimal, purely functional implementation of the Garsia–Wachs algorithm ⋮ Improved approximation algorithms for the average-case tree searching problem ⋮ The Optimal Alphabetic Tree problem revisited ⋮ Testing the optimality of alphabetic trees ⋮ Dynamic Trees with Almost-Optimal Access Cost ⋮ On the Huffman and alphabetic tree problem with general cost functions ⋮ Optimal binary search trees ⋮ On the cost of unsuccessful searches in search trees with two-way comparisons ⋮ Heuristics for optimum binary search trees and minimum weight triangulation problems ⋮ Reflections on Optimal and Nearly Optimal Binary Search Trees ⋮ Monotonicity and efficient computation of optimal dichotomous search

This page was built for publication: A New Algorithm for Minimum Cost Binary Trees