Obnoxious Centers in Graphs
Sergio Cabello, Günter Rote · SIAM Journal on Discrete Mathematics · 2010
We consider the problem of finding obnoxious centers in graphs. For arbitrary graphs with n vertices and m edges, we give a randomized algorithm with $O(n\log^{2}n+m\log n)$ expected time. For planar graphs, we give algorithms with $O(n\log n)$ expected time and $O(n\log^{3}n)$ worst-case time. For graphs with bounded treewidth, we give an algorithm taking $O(n\log n)$ worst-case time. The algorithms make use of parametric search and several results for computing distances on graphs of bounded treewidth and planar graphs.