Abstract
This paper studies the problem of finding the 1-center on a graph where vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax-regret solution, which minimizes the worst-case loss in the objective function. Averbakh and Berman had an O(mn 2 log n)-time algorithm for the problem on a general graph. On a tree, the time complexity of their algorithm becomes O(n 2 ). In this paper, we improve these two bounds to O(mnlog n) and O(nlog 2 n), respectively.© 2006 Springer-Verlag Berlin/Heidelberg.