The obnoxious center problem on a tree

The obnoxious center problem in a graph G asks for a location on an edge of the graph such that the minimum weighted distance from this point to a vertex of the graph is as large as possible. We derive algorithms with linear running time for the cases when G is a path or a star, thus improving previous results of Tamir [SIAM J. Discrete Math, 1 (1988), pp. 377-396]. For subdivided stars we present an algorithm of running time O (n log n). For general trees, we improve an algorithm of Tamir [SIAM J. Discrete Math, 1 (1988), pp. 377-396] by a factor of log n. Moreover, a linear algorithm for the unweighted center problem on an arbitrary tree with neutral and obnoxious vertices is described.