The continuous center set of a network (Q757234)

Let N be a simple undirected connected network with n vertices and m edges. A local continuous center of an edge is a point minimizing the remoteness of x when x ranges over this edge (the remoteness of x being the distance from x to the farthest point of N). First of all, the authors develop a method to find the local continuous centers of an edge. The computational complexity of this algorithm is shown to be equal to O(m log m). Then, a second algorithm using the first one is given to determine the continuous center set and the continuous radius of N in \(O(m^ 2\log m)\) operations in the worst case (the continuous radius is the minimal value of the remoteness of x for any \(x\in N\) whereas any local continuous center the remoteness of which is equal to the continuous radius is termed a continuous center). Elimination techniques are described in order to accelerate the algorithm.