| Presentation | 2005-04-18 Lowering Eccentricity of a Tree by Node-Upgrading Toshihide IBARAKI, Xiao-guang YANG, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The eccentricity lowering problem is to reduce the eccentricity of a communication network within a given bound, by upgrading some nodes (i.e., shrinking the lengths of the edges linking to such nodes), where we want to minimize the required cost. We consider two types of node-upgrading strategies, i.e., the continuous upgrading and the discrete upgrading, 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 NP-hard for the general graph. When the graph is a tree, we present an O(|V|^2) time algorithm to solve the eccentricity lowering problem under the continuous upgrading strategy. However, the problem under the discrete upgrading strategy is still NP-hard even if the graph is a line. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Communication network / eccentricity / node-upgrading / tree / line |
| Paper # | COMP2005-8 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2005/4/11(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Lowering Eccentricity of a Tree by Node-Upgrading |
| Sub Title (in English) | |
| Keyword(1) | Communication network |
| Keyword(2) | eccentricity |
| Keyword(3) | node-upgrading |
| Keyword(4) | tree |
| Keyword(5) | line |
| 1st Author's Name | Toshihide IBARAKI |
| 1st Author's Affiliation | School of Science and Technology, Kwansei Gakuin University() |
| 2nd Author's Name | Xiao-guang YANG |
| 2nd Author's Affiliation | Institute of Systems Science, Academy of Mathematics and Systems Science, Chinese Academy of Sciences |
| Date | 2005-04-18 |
| Paper # | COMP2005-8 |
| Volume (vol) | vol.105 |
| Number (no) | 7 |
| Page | pp.pp.- |
| #Pages | 9 |
| Date of Issue | |