### 博碩士論文 101221023 詳細資訊

 以作者查詢圖書館館藏 、以作者查詢臺灣博碩士 、以作者查詢全國書目 、勘誤回報 、線上人數：34 、訪客IP：3.235.25.169

(Target Set Selection Problem on Paths and Grids)

 ★ 圓環面網路上的病毒散播 ★ 以2D HP 模型對蛋白質摺疊問題之研究 ★ On Steiner centers of graphs ★ On the Steiner medians of a block graph ★ 圖形列表著色 ★ 秩為5的圖形 ★ Some results on distance-two labeling of a graph ★ 關於非奇異線圖的樹 ★ On Minimum Strictly Fundamental Cycle Basis ★ 目標集選擇問題 ★ 超立方體圖與格子圖上的目標集問題 ★ 圖形環著色數的若干等價定義 ★ 網格圖上有效電阻計算方法的比較 ★ 數樹：方法綜述 ★ d 維立方體圖上有效電阻與首達時間的計算方法

1. 本電子論文使用權限為同意立即開放。
2. 已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
3. 請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

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.

★ 格子圖
★ 目標集問題

★ grids
★ TTS
★ Target set

2 Examples for TSS Problem 3
3 TSS Problem on Path 10
References 16

target set selection, Theoret. Comput. Sci., 411(2010), pp. 4017-4022.
[2] S. S. Adams, D. S. Troxell, and S. L. Zinnen, Dynamic monopolies and feedback
vertex sets in hexagonal grids, Comput. and Math. Appl., 62(2011), pp. 4049-4057.
[3] Bela Bollobas, The Art of Mathematics Coffee Time in Memphis, Cambridge University Pressm, 2006, pp. 171-172.
[4] E. Berger, Dynamic monopolies of constant size, J. Combin. Theory Ser. B, 83(2001),
pp. 191-200.
[5] O. Ben-Zwi, D. Hermelin, D. Lokshtanov, and I. Newman, Treewidth governs the
complexity of target set selection, Discrete Optim., 8(2011), pp. 87-96.
[6] J. Balogh and G. Pete, in Proceedings of the Eighth International Conference ′Random
Structures and Algorithms′ (Poznan, 1997), Random Structures Algorithms, 13(1998) pp. 409-422.
[7] N. Chen, On the approximability of influence in social networks, SIAM J. Discrete
Math., 23(2009), pp. 1400-1415.
[8] C. -Y. Chaing, L. -H. Huang, B. -J. Li, J. Wu, and H. -G. Yeh, Some Results on the
Target Set Selection Problem, J. Comb. Optim., to appear.
[9] P. A. Dreyer and F. S. Roberts, Irreversible k-threshold processes: Graph-theoretical
threshold models of the spread of disease and of opinion, Discrete Applied Math.,
157(2009), pp. 1615-1627.
[10] P. Flocchini, F. Geurts, and N. Santoro, Optimal irreversible dynamos in chordal rings, Discrete Appl. Math., 113(2001), pp. 23-42.
[11] P. Flocchini, R. Kralovi?, P. Ru?i?ka, A. Roncato, and N. Santoro, On time versus
size for monotone dynamic monopolies in regular topologies, J. Discrete Algorithms,
1(2003), pp. 129-150.
[12] P. Flocchini, E. Lodi, F. Luccio, L. Pagli, and N. Santoro, Dynamic monopolies in tori, Discrete Appl. Math., 137(2004), pp. 197-212.
[13] P. Flocchini, Contamination and Decontamination in Majority-Based Systems, J. Cell.
Autom., 4(2009), pp. 183-200.
[14] D. Kempe, J. Kleinberg, and E. Tardos, Maximizing the spread of influence through
a social network, in Proceedings of the 9th ACM SIGKDD International Conference
on Knowledge Discovery and Data Mining, 2003, pp. 137-146.
[15] D. Kempe, J. Kleinberg, and E. Tardos, Influential nodes in a diffusion model for
social networks, in Proceedings of the 32th International Colloquium on Automata,
Languages and Programming, 2005, pp. 1127-1138.
[16] F. Luccio, Almost exact minimum feedback vertex set in meshes and butterflies, Inform. Process. Lett., 66(1998), pp. 59-64.
[17] F. Luccio, L. Pagle, and H. Sanossian, Irreversible dynamos in butterflies, in proceedings of the 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 1999, pp. 204-218.
[18] D. Peleg, Size bounds for dynamic monopolies, Discrete Appl. Math., 86(1998) pp.
263-273.
[19] D. Peleg, Local majorities, coalitions and monopokies in graphs: A review, Theoret.
Comput. Science, 282(2002) pp. 231-257.
[20] D. A. Pike and Y. Zou, Decycling Cartesian products of two cycles, SIAM J. Discrete
Math., 19(2005) pp. 651-663.
[21] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math.,
312(2012) pp. 1136-1143.