Sergio Cabello and Günter Rote:

Obnoxious centers in graphs

1. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, January 2007, pp. 98–107. doi:10.1145/1283383.1283395
2. SIAM Journal on Discrete Mathematics 24 (2010), 1713–1730. doi:10.1137/09077638X

Abstract

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 with O(n log²n + m log n) expected time. For planar graphs, we give algorithms with O(n log n) expected time and O(n log³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.