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

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：129

、訪客IP：18.221.243.112

姓名

郭瀚文(Han-wun Guo) 查詢紙本館藏

畢業系所

數學系

論文名稱

路徑圖與格子圖上的目標集問題
(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	★ 目標集選擇問題
★ 超立方體圖與格子圖上的目標集問題	★ 圖形環著色數的若干等價定義
★ 網格圖上有效電阻計算方法的比較	★ 數樹：方法綜述
★ 拉普拉斯居中度研究概述	★ 信息居中度研究簡要回顧

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

本論文主要在處理路徑圖 (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

論文目次

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

參考文獻

[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.
[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.

指導教授

葉鴻國(Hong-Gwa Yeh)

審核日期

2014-6-30

推文