OBNOXIOUS CENTERS IN GRAPHS

摘要

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(nlog 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.