請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9737
標題: | 平面網路上防疫問題之近似演算法 An Approximation Algorithm for the Inoculation Problem for Planar Networks |
作者: | Kuan-Kai Chiu 邱冠凱 |
指導教授: | 呂學一(Hsueh-I Lu) |
關鍵字: | 電腦病毒模型,網路安全與經濟,圖形分割, Computer virus model,Economics of network security,Graph partition, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/9737 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf | 398.67 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。