##
Rainer E. Burkard, Yixun Lin, Helidon Dollani, and Günter Rote:

#
The obnoxious center problem on a tree

*SIAM Journal on Discrete Mathematics* **14** (2001),
498–509.
doi:10.1137/S0895480198340967
###
Abstract

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 (1988). For subdivided stars we
present an algorithm of running time `O`(`n` log `n`). For
general trees, we improve an algorithm of Tamir by a factor of log `n`.
Moreover, we describe a linear algorithm for the unweighted center problem
on an arbitrary tree with neutral and obnoxious vertices.
Last update: April 4, 2002.