Lowering eccentricity of a tree by node upgrading
Toshihide Ibaraki, Yann Vaxès, Xiaoguang Yang · Networks · 2005
Abstract 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