ICS Theory Group

ICS 269, Spring 2005: Theory Seminar

22 Apr 2005:
The Maximum-Mean Subtree
Josiah Carlson

In this talk, we define the Maximum-Mean Subtree problem on trees, an equivalent reformulation of the Fractional Prize-Collecting Steiner Tree Problem on Trees. We describe an algorithm that solves the Maximum-Mean Subtree problem, and prove that our algorithm runs in O(n) time in the worst case, improving a previous O(n log n) algorithm.

This talk is a presentation of a paper by David Eppstein and Josiah Carlson, which was submitted to WADS 2005.