摘要
This paper studies the problem of finding a path centdian on a tree in which 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. Puerto et al. had an O(n 5 logn)-time algorithm for this problem. In this paper, we first show that there is a special case which their algorithm does not handle and it is easy to modify their algorithm to cope with this exception. Then, we further present an improved O(n 4 )-time algorithm.