Finding a core of a tree with pos/neg weight

Let T = (V, E) be a tree. A core of T is a path P, for which the sum of the weighted distances from all vertices to this path is minimized. In this paper, we consider the semi-obnoxious case in which the vertices have positive or negative weights. We prove that, when the sum of the weights of vertices is negative, the core must be a single vertex and that, when the sum of the vertices’ weights is zero there exists a core that is a vertex. Morgan and Slater (J Algorithms 1:247–258, <CitationRef CitationID="CR13">1980</CitationRef>) presented a linear time algorithm to find the core of a tree with only positive weights of vertices. We show that their algorithm also works for semi-obnoxious problems. Copyright Springer-Verlag 2012