| Presentation | 2015-03-02 Polynomial-time Approximation Algorithm for Finding Protected Nodes against Crash of Nodes Tomomi MATSUI, Hiroyoshi MIWA, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | In recent years, the Internet plays a important role as a social infrastructure. Therefore network service providers are required to design and operate high reliable networks. However, in many actual networks, there is the risk of telecommunication blackout by nodes failure or attack. Moreover, since such network has a scale-free property, if high degree nodes are selectively attacked, the remaining network is fragmented to many small connected component. Against these problem, there is a method that changes the disposition of network topology. However, it is more realistic to make nodes robust by backup facility than the method. It is desirable that all nodes have their backup facility. However, it needs much cost; therefore, it is important to determine a minimum set of nodes to maintain requested quality. In this paper, we propose an approximation algorithm with the approximation ratio of k for the problem restricted to the case that at most k nodes simultaneously fail. Moreover, we evaluate the performance of the approximation algorithm by using actual network topologies. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Node protection / Network design / Optimization / Algorithm |
| Paper # | NS2014-186 |
| Date of Issue |
| Conference Information | |
| Committee | NS |
|---|---|
| Conference Date | 2015/2/23(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 | Network Systems(NS) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Polynomial-time Approximation Algorithm for Finding Protected Nodes against Crash of Nodes |
| Sub Title (in English) | |
| Keyword(1) | Node protection |
| Keyword(2) | Network design |
| Keyword(3) | Optimization |
| Keyword(4) | Algorithm |
| 1st Author's Name | Tomomi MATSUI |
| 1st Author's Affiliation | Graduate School of Science and Technology, Kwansei Gakuin University() |
| 2nd Author's Name | Hiroyoshi MIWA |
| 2nd Author's Affiliation | Graduate School of Science and Technology, Kwansei Gakuin University |
| Date | 2015-03-02 |
| Paper # | NS2014-186 |
| Volume (vol) | vol.114 |
| Number (no) | 477 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |