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


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.
  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject
Last update: April 4, 2002.