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.