An Approximation Algorithm for the Inoculation Problem for Planar Networks
Date Issued
2008
Date
2008
Author(s)
Chiu, Kuan-Kai
Abstract
For numbers c and k and an n-node graph G, the inoculation problem is to compute an $S$ consisting of at most k nodes of G such that c*m+(1/n)*sum_i n_i^2 is minimized, where m is the cardinality of S and n_i is the number of nodes in the i-th connected component of GS. The best previously known result, due to Aspnes, Chang, and Yampolskiy, for this NP-complete problem is an O(log^{1.5}n)-approximation algorithm. In the present article, we focus on the special case that G is planar: We show that the problem remains NP-complete and give an O(log n)-approximation algorithm for the problem.
Subjects
Computer virus model
Economics of network security
Graph partition
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-97-R95922121-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):96e42c19cccbb1f10a789beb73d554dc