Efficient Algorithms for the 2-Center Problems

This paper achieves O(n 3 log log n/ log n) time for the 2- center problems on a directed graph with non-negative edge costs under the conventional RAM model where only arithmetic operations, branching operations, and random accessibility with O(log n) bits are allowed. Here n is the number of vertices. This is a slight improvement on the best known complexity of those problems, which is O(n 3 ). We further show that when the graph is with unit edge costs, one of the 2-center problems can be solved in O(n 2.575) time