## Sergio Cabello and Günter Rote:

# Obnoxious centers in graphs

- 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
*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^{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.

Last update: December 17, 2010.