Lowering eccentricity of a tree by node upgrading
文献类型：期刊论文
| 作者 | Ibaraki, T; Vaxes, Y; Yang, XG |
| 刊名 | NETWORKS
 |
| 出版日期 | 2005-07-01 |
| 卷号 | 45期号:4页码:232-239 |
| 关键词 | eccentricity node upgrading edge upgrading discrete upgrading strategy continuous upgrading strategy tree line |
| ISSN号 | 0028-3045 |
| DOI | 10.1002/net.20069 |
| 英文摘要 | 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 0(1 VI log I VI) 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. (c) 2005 Wiley Periodicals, Inc. |
| WOS研究方向 | Computer Science ; Operations Research & Management Science |
| 语种 | 英语 |
| WOS记录号 | WOS:000229994000009 |
| 出版者 | JOHN WILEY & SONS INC |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/1790]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Ibaraki, T |
| 作者单位 | 1.Kwansei Gakuin Univ, Sch Sci & Technol, Dept Informat, Sanda 6691337, Japan 2.Univ Mediterranee, Fac Sci Luminy, Lab Informat Fondamentale Marseille, F-13288 Marseille, France 3.Chinese Acad Sci, Acad Math & Syst Sci, Inst Syst Sci, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Ibaraki, T,Vaxes, Y,Yang, XG. Lowering eccentricity of a tree by node upgrading[J]. NETWORKS,2005,45(4):232-239. |
| APA | Ibaraki, T,Vaxes, Y,&Yang, XG.(2005).Lowering eccentricity of a tree by node upgrading.NETWORKS,45(4),232-239. |
| MLA | Ibaraki, T,et al."Lowering eccentricity of a tree by node upgrading".NETWORKS 45.4(2005):232-239. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。