The Obnoxious Center Problem on a Tree
Rainer E. Burkard, Helidon Dollani, Yixun Lin, Günter Rote · SIAM Journal on Discrete Mathematics · 2001
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 [SIAMJ. 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.