David Eppstein - Publications

Publications with Josiah Carlson

• The weighted maximum-mean subtree and other bicriterion subtree problems.
  J. Carlson and D. Eppstein.
  arXiv:cs.CG/0503023.
  Proc. 10th Scand. Worksh. Algorithm Theory (SWAT 2006).
  Springer, Lecture Notes in Comp. Sci. 4059, 2006, pp. 397–408.

  We give a linear time algorithm for pruning a node-weighted tree to maximize the average node weight of the pruned subtree; this problem was previously studied under the less obvious name "The Fractional Prize-Collecting Steiner Tree Problem on Trees".

• Trees with convex faces and optimal angles.
  J. Carlson and D. Eppstein.
  arXiv:cs.CG/0607113.
  14th Int. Symp. Graph Drawing, Karlsruhe, Germany, 2006.
  Springer, Lecture Notes in Comp. Sci. 4372, 2007, pp. 77–88.

  We consider drawings of trees which, if the leaf edges were extended to infinite rays, would form partitions of the plane into unbounded convex polygons. For such a drawing the edges may be chosen independently without any possibility of edge crossing. We show how to choose the angles of such drawings to optimize the angular resolution of the drawing.

  (GD06 talk slides)

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.