Lowering eccentricity of a tree by node upgrading

The eccentricity lowering problem is to reduce the eccentricity of a network by upgrading some nodes (that is, shrinking the lengths of the edges incident to such nodes). We consider two types of node-upgrading strategies, that is, a continuous upgrading strategy and a discrete upgrading strategy, where the improvement under the first strategy is a continuous variable, and the improvement under the second strategy is a fixed amount. These problems are hard even to approximate, for general graphs. Therefore, we restrict our attention to graphs with simple structures. Assuming that the graph G = (V,E) is a tree, we show that the eccentricity lowering problem under the continuous node-upgrading strategy can be reduced to the eccentricity lowering problem under the continuous edge-upgrading strategy, and can be solved by an O(|V| log |V|) time algorithm. We also show that the problem for a tree is NP-hard under the discrete upgrading strategy, but admits a fully polynomial approximation scheme, if the graph is a line. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 45(4), 232–239 2005