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


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

  PostScript file (gzipped)   pdf file
other papers about this subject
Last update: December 17, 2010.