Abstract
Let p ≥ 2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p - 1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O (n 2 )-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min {p, n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b / a | a ∈ [1, m], b ∈ B} such that F (z) ≥ t. We give an O (n + t F × (log n + log m))-time algorithm for this problem, where t F is the time required to evaluate the function value F (z) for any real number z. © 2009 Elsevier B.V. All rights reserved.