Minimax Trees in Linear Time with Applications

Minimax Trees in Linear Time with Applications,10.1007/978-3-642-10217-2_28,Lecture Notes in Computer Science,Pawel Gawrychowski,Travis Gagie

Minimax Trees in Linear Time with Applications   (Citations: 4)
BibTex | RIS | RefWorks Download
A minimax tree is similar to a Human tree except that, instead of minimizing the weighted average of the leaves' depths, it min- imizes the maximum of any leaf's weight plus its depth. Golumbic (1976) introduced minimax trees and gave a Human-like, O(n logn)-time algo- rithm for building them. Drmota and Szpankowski (2002) gave another O(n logn)-time algorithm, which takes linear time when the weights are already sorted by their fractional parts. In this paper we give the rst linear-time algorithm for building minimax trees for unsorted real weights.
Journal: Lecture Notes in Computer Science - LNCS , pp. 278-288, 2009
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: