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