Name
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 |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1002/net.v45:4 | Networks |
Keywords | Field | DocType |
tree,eccentricity,line | Graph,Mathematical optimization,Combinatorics,Line graph,Polynomial,Eccentricity (behavior),Continuous variable,Mathematics | Journal |
Volume | Issue | ISSN |
45 | 4 | 0028-3045 |
Citations | PageRank | References |
3 | 0.50 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Toshihide Ibaraki | 1 | 2593 | 385.64 |
| Yann Vaxès | 2 | 204 | 19.11 |
| Xiaoguang Yang | 3 | 250 | 34.56 |