平面網路上防疫問題之近似演算法

An Approximation Algorithm for the Inoculation Problem for Planar Networks

邱冠凱(Kuan-Kai Chiu)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.01916

摘要

無資料

關鍵字

電腦病毒模型 ； 網路安全與經濟 ； 圖形分割

並列摘要

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.

並列關鍵字

Computer virus model ； Economics of network security ； Graph partition

參考文獻

[1] E. Amir, R. Krauthgamer, and S. Rao. Constant factor approximation of vertex-cuts in planar graphs. In Proceedings of the 35th Annual ACM Symposium on Theory of

[2] R. Anderson and T. Moore. The economics of information security. Science Magazine, 314(5799):610–613, October 2006.

Lecture Notes in Computer Science, pages 68–91. Springer, 2007.

[4] J. Aspnes, K. Chang, and A. Yampolskiy. Inoculation strategies for victims of viruses and the sum-of-squares partition problem. In Proceedings of the 16th Annual

ACM-SIAM Symposium on Discrete Algorithms, pages 43–52, Vancouver, British Columbia, Canada, January 23-25 2005.