路徑圖與格子圖上的目標集問題

Target Set Selection Problem on Paths and Grids

郭瀚文(Han-wun Guo)

指導教授 ： 葉鴻國

國立中央大學/理學院/數學系/碩士(2014年)

摘要

本論文主要在處理路徑圖 (Path) 上的 Target set Selection Problem (TSS Problem)，另外對 Pn□Pm 圖上也得到一些結果。我們在 TSS Problem 上考慮兩類感染方式：並行感染規則 I 與並行感染規則 II。
在並行感染規則 I 下，將已有的 Theorem 1 至 Theorem 3 ([3], [6]) 從 Pn□Pn 推廣到 Pn□Pm，並給出不等式等號成立的充分條件。在並行感染規則 II 下，討論並行感染規則 II 的性質 (遞增性，圖形與子圖的關係)，在圖形為 path 時，討論 min-seed 在子圖中的下界，對於在 path 上一般性的情形，其中 a_i≥2 的情形可以得到結果，一般性的情形 a_i≥0 還沒有解決，但可以推論出問題的關鍵在於〖 a〗_i≥1 的情形。

關鍵字

路徑圖 ； 格子圖 ； 目標集問題

並列摘要

In this paper, we are focus on the Target set Selection Problem (TSS Problem) on path. We also get some results on Pn□Pm. Consider two different rules of Bootstrap Percolation:
Rule I and Rule II
Under Rule I, we generalize Theorem 1, Theorem 2 and Theorem 3 ([3], [6]) from Pn□Pn
to Pn□Pm.. Furthermore, we give some sufficient conditions for inequality such that equality holds. On the other hand, we have some properties under Rule II and results on path.

並列關鍵字

path ； grids ； TTS ； Target set

參考文獻

[14] D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of influence through

[1] E. Ackerman, O. Ben-Zwi, and G. Wolfovitz, Combinatorial model and bounds for

target set selection, Theoret. Comput. Sci., 411(2010), pp. 4017-4022.

[4] E. Berger, Dynamic monopolies of constant size, J. Combin. Theory Ser. B, 83(2001),

complexity of target set selection, Discrete Optim., 8(2011), pp. 87-96.